Be careful with hashmaps

As you remember from long ago hashes are O(1) best case, but can be O(n) if you get hash collisions. And if you're adding n new entries that means O(n^2).

I thought I'd take a look at the hash_set/hash_map GNU C++ extension.

In /usr/include/c++/4.4.3/backward/hash_fun.h: 
1
2
3
4
5
6
7
8
  inline size_t
  __stl_hash_string(const char* __s)
  {
    unsigned long __h = 0;
    for ( ; *__s; ++__s)
      __h = 5 * __h + *__s;
    return size_t(__h);
  }
Test program that loads some strings: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<time.h>
#include<iostream>
#include<hash_set>

double getclock()
{
  struct timespec ts;
  clock_gettime(CLOCK_MONOTONIC, &ts);
  return ts.tv_sec + ts.tv_nsec / 1e9;
}

_GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
template<> struct hash< ::std::string> {
  size_t operator()(const ::std::string& x) const {
    return hash<const char*>()(x.c_str());
  }
};
_GLIBCXX_END_NAMESPACE

int main()
{
  __gnu_cxx::hash_set<std::string> the_set;
  double start = getclock();

  while (std::cin.good()) {
    std::string line;
    getline(std::cin, line);

    the_set.insert(line);
  }
  std::cout << "Size: " << the_set.size() << std::endl
            << "Time: " << getclock()-start << std::endl;
}
Running the loader with different inputs: 
$ ./generateCollisions 5 > coll-5
$ ./generateCollisions 6 > coll-6
$ wc -l coll-5 coll-6
  13826 coll-5
 149696 coll-6
 163522 total
$ seq -f "%06.0f" 13826 > num-5
$ seq -f "%06.0f" 149696 > num-6
$ ./load < num-5
Size: 13827
Time: 0.0148379
$ ./load < num-6
Size: 149697
Time: 0.135555
$ ./load < coll-5
Size: 13827
Time: 1.44663
$ ./load < coll-6
Size: 149697
Time: 212.009
That's going from 0.14 seconds to over 3 and a half minutes.

Collision generator

Left as an exercise to the reader. My code is too ugly to release.

Summary

Nothing new, just a friendly reminder to treat input data as untrusted. Think of all the places where you use a hash map. How many of the keys come straight from untrusted sources? (user names, photo tags, JSON or XML data that at some point is shoved into suitable data structures, etc...)

Links

Comments

Post a Comment

Popular posts from this blog

TPM chip protecting SSH keys - properly

Not long after getting my TPM chip to protect SSH keys in a recent blog post , it started to become obvious that OpenCryptoKi was not the best solution. It's large, complicated, and, frankly, insecure. I dug in to see if I could fix it, but there was too much I wanted to fix, and too many features I didn't need. So I wrote my own. It's smaller, simpler, and more secure. This post is about this new solution. Why not Opencryptoki? It generates at least some keys in software. As I've explained earlier, I want to generate the keys in hardware . It generates migratable keys. This is hardcoded, and some people obviously want migratable keys (for backup purposes). So a fix would have to involve supporting both. Opencryptoki has no way to send such parameters from the command line key generator to the PKCS11 library. So not only would I have to implement the setting , but the whol...
Read more

Next-hop resolution and point-to-point

Image
I had this blog post lying around as a draft for a long time. I didn't think it was was "meaty" enough yet, but since I'm no longer a network consultant I don't think it'll become any meatier. So here it goes. Here I will describe the process of L3-to-L2 mapping, or next-hop resolution and how it works with point-to-point circuits like PPP, ATM and Frame relay. It's the process of finding out what to actually do with a packet once the relevant routing table entry has been identified. It's deceptively simpler than on a LAN segment, but since people generally learn Ethernet before they learn point-to-point nowadays I'm writing it anyway. When a packet is to be sent to an address on the same subnet a L3-to-L2 mapping is done to look up the L2 destination address (if any) to apply. The packet is then encapsulated in a L2 frame and sent out the interface. On a normal Ethernet LAN segment ARP is use...
Read more

OpenSSH certificates

The documentation for OpenSSH certificates (introduced in OpenSSH 5.4) are, shall we say, a bit lacking. So I'm writing down the essentials of what they are and how to use them. What they are NOT They're not SSH PubkeyAuthentication In other words if your .pub file doesn't end in -cert.pub and you haven't used ssh-keygen -s, then you aren't using certificates. They're not SSL Still the same SSH protocol. They're not PEM, x509 ASN.1 or any other insane format This means you cannot get your keys signed by Verisign or any other root CA. And you cannot use multiple levels of CA. They're not easy to google for Most hits will be about normal pubkey authentication. Some will be about older patches to one SSH implementation or another that added some form of PKI, even x509 support. You'll probably have the most luck googling for "ssh-keygen -s" (with quotes). What they do Sign host keys ...
Read more