Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Diving into the world of hash tables

zeroequalsfalse.press

Post reply on HN
Print view View original

31–40 of 107 posts

Re: Diving into the world of hash tables

#31

Post by robmccoll »

Cyph0n wrote: post #20

Quick question: are there special hash functions that are optimized for use in hash tables? Or do typical hash table implementations in e.g. Python just use standard hash functions like MD5? Edit: It's 100% clear now. Thanks for the great answers everyone!

Typically the hash functions that you are familiar with due to cryptographic or data consistency use (SHA family, MD family, etc) do not make for good hash table choices because they produce hashes that are much larger than needed and are slow to compute so that they have better cryptographic properties (extremely low collision, no information leakage about inputs, difficulty of guessing inputs). When picking a hash function for a hash table, you want a function that makes a hash just big enough and with low enough collisions while still being fast and easily dealing with variable length keys. This could he something as simple as byte-wise XOR or addition with some shifting as you iterate the key followed by a mod or even bitwise AND mask to pick an index.

Re: Diving into the world of hash tables

#33

Post by YZF »

VHRanger wrote: post #26

If you care about performance, it's important to note how the underlying representation of a dictionary data structure. For instance, the unordered_hash_map in C++ is based around a linked list of key/value pair buckets. This means iterating through the keys or values is very slow (lots of cache misses!), but insertion is fast. Retrieving a key is O(logn) but a very slow O(logn), because of the cache misses. Other im…

You mean insertion into a bucket when there's a collision? And your n is the number of entries in the list? But n should always be very small relative to the total number of items in the hash map such that overall insertion and lookups are O(1).

Re: Diving into the world of hash tables

#35

Post by obstinate »

VHRanger wrote: post #26

If you care about performance, it's important to note how the underlying representation of a dictionary data structure. For instance, the unordered_hash_map in C++ is based around a linked list of key/value pair buckets. This means iterating through the keys or values is very slow (lots of cache misses!), but insertion is fast. Retrieving a key is O(logn) but a very slow O(logn), because of the cache misses. Other im…

> sorted vector of keys . . . reserve necessary memory and sort it . . . unsorted coindexed arrays . . .

Most of the things you mentioned are not hash tables, but members of a parent concept, dictionaries. Hash tables all by definition involve some sort of hashing of the key. The two main categories of hash table are chained hash tables (std::unordered_map does this, at least in the implementations I'm aware of) and open addressed hash tables, which use probing instead of secondary data structures to resolve conflicts.

Re: Diving into the world of hash tables

#36

Post by floogtheunfound »

douche wrote: post #27
slig wrote: post #23

Earlier quoted context omitted.

> While that's true you could implement one that way, it's very nice to have the set operations implemented Unrelated, but does anyone know why the new JavaScript set implementation is so limited? Why didn't they bother doing this right?

Because it is JavaScript, and there's some kind of unspoken rule about not doing things properly and instead releasing broken things.

I’m shocked this isn’t being aggressively down voted...oh wait... it’s bashing js and not bashing haskell...nvm

Re: Diving into the world of hash tables

#37

Post by lsadam0 »

mabbo wrote: post #5

I think when the author says "underrated", what they mean is "I didn't realize how important this is". Hash tables are used everywhere, by everyone, for a lot of things. Maybe they don't give it enough time in school for people to realize it is the king of practical software development.

Really. Hash tables are one of my most used data structures.

Re: Diving into the world of hash tables

#38

Post by VHRanger »

obstinate wrote: post #35
VHRanger wrote: post #26

If you care about performance, it's important to note how the underlying representation of a dictionary data structure. For instance, the unordered_hash_map in C++ is based around a linked list of key/value pair buckets. This means iterating through the keys or values is very slow (lots of cache misses!), but insertion is fast. Retrieving a key is O(logn) but a very slow O(logn), because of the cache misses. Other im…

> sorted vector of keys . . . reserve necessary memory and sort it . . . unsorted coindexed arrays . . . Most of the things you mentioned are not hash tables, but members of a parent concept, dictionaries. Hash tables all by definition involve some sort of hashing of the key. The two main categories of hash table are chained hash tables (std::unordered_map does this, at least in the implementations I'm aware of) and…

You can implement the sorted vector of keys with a hash function instead of a coindexed vector of values. It still keeps most of the properties we like, especially if doing the coindex-sort operation is too expensive for some reason.

Re: Diving into the world of hash tables

#39

Post by Cyph0n »

mabbo wrote: post #5

I think when the author says "underrated", what they mean is "I didn't realize how important this is". Hash tables are used everywhere, by everyone, for a lot of things. Maybe they don't give it enough time in school for people to realize it is the king of practical software development.

Agreed. I mean, for example, doesn't the entire Lua language revolve around hash tables?

Re: Diving into the world of hash tables

#40

Post by obstinate »

VHRanger wrote: post #38
obstinate wrote: post #35

Earlier quoted context omitted.

> sorted vector of keys . . . reserve necessary memory and sort it . . . unsorted coindexed arrays . . . Most of the things you mentioned are not hash tables, but members of a parent concept, dictionaries. Hash tables all by definition involve some sort of hashing of the key. The two main categories of hash table are chained hash tables (std::unordered_map does this, at least in the implementations I'm aware of) and…

You can implement the sorted vector of keys with a hash function instead of a coindexed vector of values. It still keeps most of the properties we like, especially if doing the coindex-sort operation is too expensive for some reason.

> You can implement the sorted vector of keys with a hash function instead of a coindexed vector of values

So you're saying you're going to hash the keys, then sort them according to the hash, with tie breaking on the key itself? I'm not aware of any sorted table that does this, but I'm sure some exist. I suppose you'd get something of a win if N was large, and the keys had long common prefixes, and you didn't care about the ordering property.

But in that case you'd probably use an actual hash table, not the algorithm you just described. Unless there's something I'm missing.

Post reply on HN