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

91–100 of 107 posts

Re: Diving into the world of hash tables

#91

Post by ramchip »

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…

> a good strategy is to reserve the necessary memory in an array, fill it with keys/values, sort it once over the keys and coindex the value array

This explanation confuses me. Is there one or two arrays? What does "coindex" mean?

Re: Diving into the world of hash tables

#92

Post by dom0 »

ramchip wrote: post #91
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…

> a good strategy is to reserve the necessary memory in an array, fill it with keys/values, sort it once over the keys and coindex the value array This explanation confuses me. Is there one or two arrays? What does "coindex" mean?

Equal indices refer to the same entity in all places. I.e. two arrays, one for the key, one for the value. The value of the key at index n in the key array is found at the same index n in the values array.

Re: Diving into the world of hash tables

#93

Post by dom0 »

hprotagonist wrote: post #4

"this is a data structure that is at the guts of basically every python object. Classes are dicts. Modules are dicts. Packages are probably dicts. Don't worry though, it's underrated!" @_@

Python (and Ruby and some others) form the category of hash table interpreters—since most things are hash tables.

Re: Diving into the world of hash tables

#94

Post by dom0 »

rdtsc wrote: post #8

It is really a basic data structure in most modern languages. Either built on or part of the standard library. I can see if this was published in late 90's but today, I don't know. And just use the built-in ones don't invent your own unless there is a very good reason for it.

> And just use the built-in ones don't invent your own unless there is a very good reason for it.

Uhm, hash tables are one of these things where plenty can be gained by tailoring the structure to the application. It's not a one-size-fits-all, and it's not nearly as easy as it would seem to make a good general-purpose HT.

Re: Diving into the world of hash tables

#95

Post by dom0 »

robmccoll wrote: post #31
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…

However, collision resistance must be still quite good for use in a general-purpose hash table or a HT that is possibly exposed to attackers, otherwise denial-of-service attacks become very easy.

Many "modern" implementations (Python, Ruby, Perl, Rust, Redis, ...) use SipHash with a random seed for this very reason.

Re: Diving into the world of hash tables

#96

Post by jwilk »

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!

Contemporary versions of Python (≥ 3.4) use SipHash for hashing strings:

https://lwn.net/Articles/574761/

OTOH, the function for hashing integers in extremely simple:

  >>> hash(42)
  42

Re: Diving into the world of hash tables

#97

Post by jwilk »

gizmo686 wrote: post #29
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!

In order to use a standard hash function, you would first need to serialize the object. I am not aware of any programing language that does this. Instead, the approach taken by (at least) Java and Python, is to define a "hash" function of objects, the classes can overwrite. The standard way of implementing such a function is to combine the hashes of the objects fields. Python advises doing this by wrapping them in a…

Python has migrated from hg to git. The current version of tupleobject.c is here:

https://github.com/python/cpython/blob/master/Objects/tupleo...

Re: Diving into the world of hash tables

#99

Post by VHRanger »

panic wrote: post #89
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…

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. Has this changed recently? Last time I used unordered_map, insertion was also slow because it had to allocate a linked list entry for every item in the hash table.

No it's part of the standard. The STL guys can't implement it differently.

Here are a few alternatives:

MCT closed_hash_map

Sparsehash's sparse_hash_map or dense_hash_map

loki::assocvector

boost::flat_hash_map

Re: Diving into the world of hash tables

#100

Post by arethuza »

obstinate wrote: post #46
VHRanger wrote: post #45

Earlier quoted context omitted.

I mean insertion into the dictionary in general.

I think you might be a little confused. Even in hash tables with chaining, one does not tend to spend much time traversing linked lists, because the typical bucket will have only one member. This depends on the load factor of the table, but most practical implementations will eventually rebucket and rehash if their load factor grows too high. "Getting the key loaded" -- i.e. finding the memory location that contains…

The early versions of String.hashCode in java only looked at the first 16 characters of the string - when used for things like URLs this led to rather poor performance!

https://en.wikipedia.org/wiki/Java_hashCode()#The_java.lang....

Post reply on HN