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

101–107 of 107 posts

Re: Diving into the world of hash tables

#101

Post by misja111 »

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…

Even if the typical bucket has 100 members, as long as this number is constant and does not go up with the size of the hash table, the performance is still O(1). And the same applies for cache misses. All these things don't really matter except if you are using hash tables with not very many elements in them.

Re: Diving into the world of hash tables

#102

Post by VHRanger »

misja111 wrote: post #101
obstinate wrote: post #46

Earlier quoted context omitted.

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…

Even if the typical bucket has 100 members, as long as this number is constant and does not go up with the size of the hash table, the performance is still O(1). And the same applies for cache misses. All these things don't really matter except if you are using hash tables with not very many elements in them.

> Even if the typical bucket has 100 members, as long as this number is constant and does not go up with the size of the hash table, the performance is still O(1).

If you mean in a chained hash table, where you chase up to 100 pointers to get the value, the performance is atrocious.

Friendly reminder: traversal of a linked list and a contiguous array are both O(n). In the real world one is two orders of magnitude faster than the other.

> All these things don't really matter except if you are using hash tables with not very many elements in them.

The lookup of a value given a key is probably the least affected operation. If all you care about is a "weak dictionary" (you only really need to store values and lookup from keys), all of this is mostly jabber. If you store the keys to iterate through, or access for some reason, all those things start to matter a whole lot.

Re: Diving into the world of hash tables

#103

Post by Eridrus »

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…

It's an interesting fiction that we tell everyone that hash tables are O(1), when in reality hash operations are typically O(n) in the key size, which is O(log n) in the value space, it's just much cheaper to have your Own(log n) operations be reading sequential bits, rather than following pointers, reading whole keys, etc.

Probably not something people usually run into, but it does show that constants matter.

Re: Diving into the world of hash tables

#104

Post by hprotagonist »

whatshisface wrote: post #90
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 has its own very cleverly optimized dict implementation: http://pybites.blogspot.com/2008/10/pure-python-dictionary-i...

hettinger's updates at pycon this year: it's better! https://www.youtube.com/watch?v=npw4s1QTmPg

Re: Diving into the world of hash tables

#105

Post by rdtsc »

bogomipz wrote: post #55
rdtsc wrote: post #16

Earlier quoted context omitted.

Though once you have hash/maps/dicts set are with reach by making sets from hashes were keys are the element and values are just true or 1 or something like that. But I think you probably meant having and using set operations effectively in day to day tasks, as in "make 2 sets and do a set different operation" instead of "do a for loop on first hash check if it is in the second, then put results in an accumulator. An…

>"Though once you have hash/maps/dicts set are with reach by making sets from hashes were keys are the element and values are just true or 1 or something like that." Can you elaborate on how you can derive a set from hashes by using values of True or 1? Might you have a link? Thanks.

> Can you elaborate on how you can derive a set from hashes by using values of True or 1? Might you have a link? Thanks.

Sure. Np!

I mean that a simplified set is just a hash where the elements of the set are keys of the hash table and the values can be anything. I used 1 or True as example.

As in adding an element would be:

   my_dict[element] = 1
Then membership check is:

   if element in my_dict
Then removal is deleting:

   del my_dict[element]
and so on.

In other words, the reason sets are sometimes not explicitly there is because they are easy to implement on top of existing data structures.

Basic operations like union, difference, intersection between two sets can be done with a few simple for loops.

But like I mentioned in other comment, there is one interesting aspect to set (and hashes) in that the element now have to be hash-able. That kind of depends how mutability and identity works in the particular language.

Re: Diving into the world of hash tables

#106

Post by draw_down »

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!" @_@

I like both kinds of data structures- maps and lists.

(Just kidding, list is but a degenerate case of map)

Re: Diving into the world of hash tables

#107

Post by bogomipz »

rdtsc wrote: post #105
bogomipz wrote: post #55

Earlier quoted context omitted.

>"Though once you have hash/maps/dicts set are with reach by making sets from hashes were keys are the element and values are just true or 1 or something like that." Can you elaborate on how you can derive a set from hashes by using values of True or 1? Might you have a link? Thanks.

> Can you elaborate on how you can derive a set from hashes by using values of True or 1? Might you have a link? Thanks. Sure. Np! I mean that a simplified set is just a hash where the elements of the set are keys of the hash table and the values can be anything. I used 1 or True as example. As in adding an element would be: my_dict[element] = 1 Then membership check is: if element in my_dict Then removal is deleting…

Thanks for the clear explanation, this makes total sense. Cheers.
Post reply on HN