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

61–70 of 107 posts

Re: Diving into the world of hash tables

#61

Post by flukus »

obstinate wrote: post #50
lsadam0 wrote: post #37

Earlier quoted context omitted.

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

In fact, what performance oriented devs need to be taught about these days is how to not use hash tables, or, more generally, dictionaries. They are a super-easy data structure to reach for, but often it is possible to arrange your data such that their use is unnecessary. One example that was brought up elsewhere in the thread is the way python looks up variables in successive scope dictionaries. This is obviously te…

> In fact, what performance oriented devs need to be taught about these days is how to not use hash tables, or, more generally, dictionaries. They are a super-easy data structure to reach for, but often it is possible to arrange your data such that their use is unnecessary.

A lot of devs are completely unaware of what's happening at the layer of abstraction below them and this is one of the ways that comes out. The number of elements it takes before hash tables are faster than iterating through an array can be surprisingly large and yet it's one of the first "optimizations" that get made.

Some other related problems are not knowing how expensive network calls are, not knowing what the ORM is doing, caching in memory even though the database already is and more. They just don't think about performance issues in code they don't write.

Re: Diving into the world of hash tables

#62

Post by tjalfi »

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…

Chandler Carruth talks about unordered_map performance[1] in his CppCon 2014 talk "Efficiency with Algorithms, Performance with Data Structures". He endorses most of the other alternatives you mentioned.

[1] https://youtu.be/fHNmRkzxHWs?t=46m39s

Re: Diving into the world of hash tables

#63

Post by VHRanger »

obstinate wrote: post #40
VHRanger wrote: post #38

Earlier quoted context omitted.

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 a…

Sorry I misspoke. Lookup is always O(1) in a hash table. But this could be a "weak dict" that is you don't actually store the keys, as long as you can reference a key through a hash you can lookup.

In the proper "data structure", we usually store the key and the value -- iteration through keys and/or values and/or pairs are probably supported operations.

Finding a key in the structure (either with binary tree search, or binary search on a sorted array, or linear lookup on an array) varies. So does iteration and most other operations.

Re: Diving into the world of hash tables

#64

Post by haburka »

obstinate wrote: post #50
lsadam0 wrote: post #37

Earlier quoted context omitted.

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

In fact, what performance oriented devs need to be taught about these days is how to not use hash tables, or, more generally, dictionaries. They are a super-easy data structure to reach for, but often it is possible to arrange your data such that their use is unnecessary. One example that was brought up elsewhere in the thread is the way python looks up variables in successive scope dictionaries. This is obviously te…

Are you serious that dictionaries are a problem for performance oriented developers?

Performance oriented devs should be concerned with bottlenecks, not incredibly minute details. There's almost no situation I can think of where smallish dictionaries are much better or worse than any other data structure when it comes to performance.

Of course, if you're writing a compiler then it can be a serious difference. Most developers don't write compilers though.

Re: Diving into the world of hash tables

#65

Post by TheAceOfHearts »

slig wrote: post #23
mcpherrinm wrote: post #14

Earlier quoted context omitted.

While that's true you could implement one that way, it's very nice to have the set operations implemented. Intersection, union, subtraction, etc. And having a uniform set type makes API signatures more consistent. Plus you may be able to optimize Set to use less space than Map .

> 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?

I think I remember reading a claim that they pushed for a small API surface in order to make sure it got through. Now that it's part of the language, anyone else can work on getting those extra features in.

You can implement most basic functionality easily enough, MDN even has an example [0]. Although I agree that it should really be part of the language.

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...

Re: Diving into the world of hash tables

#66

Post by freyr »

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.

Python essentially does this as well.

The idea is that an item is in the set if it's in the hash table. You can add, remove, or test for membership in constant average time.

Set operations still need to be built on top of this.

Re: Diving into the world of hash tables

#67

Post by hueving »

obstinate wrote: post #50
lsadam0 wrote: post #37

Earlier quoted context omitted.

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

In fact, what performance oriented devs need to be taught about these days is how to not use hash tables, or, more generally, dictionaries. They are a super-easy data structure to reach for, but often it is possible to arrange your data such that their use is unnecessary. One example that was brought up elsewhere in the thread is the way python looks up variables in successive scope dictionaries. This is obviously te…

99.999% of projects are not going to have any meaningful hot path in variable resolution.

If your program is sensitive to that, even a simple GC pause is going to destroy your performance and you need to be out of managed memory languages at that point.

There are a lot of reasons python can be slow, but this is far from one of them.

Re: Diving into the world of hash tables

#68

Post by hueving »

rectangletangle wrote: post #56
bogomipz wrote: post #53

Earlier quoted context omitted.

>"For instance `a = foo.bar.baz` in Python involves 3 hash gets (local scope, foo scope, then bar scope), and a single set operation (local scope)" Can you explain where exactly and why a set operation is performed? Thanks.

When the name `a` is assigned the value of `baz`, Python is setting a key name `a` in the local dictionary (hash table) `locals()`. Basically `a = 1` is syntactic sugar for `locals()['a'] = 1` >>> a Traceback (most recent call last): File " ", line 1, in NameError: name 'a' is not defined >>> locals()['a'] = 113 >>> a 113 >>> One interesting side-effect of this is you can assign names that are not valid Python syntax…

locals() is presented to the user as a dictionary, but is that the way cpython actually works with it internally? I've run into weird GC issues that imply it's not a normal dictionary and it's just presented to the user as one for programattic access.

Re: Diving into the world of hash tables

#69

Post by freyr »

jackweirdy wrote: post #21
OJFord wrote: post #18

Earlier quoted context omitted.

Does it really matter what the 'value' is? A set is surely implementable as a supertype of a hash, where the value is totally arbitrary; it only matters that the entry exists. With: {'A': true, 'B': false} you seem to be suggesting `B` is 'not in the set'. What's `C`?

Not in the set. You're describing the same thing as the parent comment, but you're saying "arbitrary value" which they substituted for "True"

They're not really the same thing then. In OJFord's implementation, there's a one-to-one correspondence between states: the element is a member of the set iff it exists as a key in the hash table.

In the true/false implementation, two distinct hash table states (false or key not set) map to one set state (not a member). The program must check whether the key is set, and then check its value.

Re: Diving into the world of hash tables

#70

Post by hueving »

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!

I recall reading at some point about Go having the option to use a call to AES on the crypto chip on the motherboard for fast high quality hashes, which is cool.
Post reply on HN