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

41–50 of 107 posts

Re: Diving into the world of hash tables

#41

Post by iainmerrick »

shishy wrote: post #7
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.

The author of the article does not say underrated at all from what I can see; just something the OP included in his title. Your point still stands, though.

Yeah, that's a weird title! I assumed it must be the actual title of the post, but no.

Re: Diving into the world of hash tables

#42

Post by rectangletangle »

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.

Nearly every expression in high-level languages relies on multiple hash lookups. This is part of the reason these languages are regarded as "slow." I suppose you could use a tree in place, and get reasonable performance. However the hash table's nature allows you to pretty much throw more memory at the problem in exchange for speed (though this is hardly unique to this particular data structure).

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). This is part of the reason Python programs can be optimized by assigning a deep attribute lookup to the local scope outside of a loop's scope, and it will yield improved performance relative to doing the deep attribute lookup inside the loop's scope.

  a = foo.bar.baz
  for _ in range(20):
      print(a)
vs

  for _ in range(20):
      print(foo.bar.baz)

Re: Diving into the world of hash tables

#43

Post by iainmerrick »

OJFord wrote: post #13
fenomas wrote: post #9

Mods, can we get a title change? As I write this every comment is taking issue with the "underrated", which isn't claimed in the article.

Though, in this case, changing it from the original does seem warranted. (This was just another bad choice...)

What's wrong with leaving it unchanged? The blog post title seems fine.

Re: Diving into the world of hash tables

#44

Post by throwaway2016a »

Cyph0n wrote: post #39
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?

Same with PHP.

Re: Diving into the world of hash tables

#45

Post by VHRanger »

YZF wrote: post #33
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).

I mean insertion into the dictionary in general.

Re: Diving into the world of hash tables

#46

Post by obstinate »

VHRanger wrote: post #45
YZF wrote: post #33

Earlier quoted context omitted.

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).

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 key -- is O(1) on average in all practical hash tables. It does not typically require any traversal at all.

You keep on talking about ordered tables like red black trees, as in this comment, which is another sign that makes me wonder if you might be confused.

Re: Diving into the world of hash tables

#47

Post by iainmerrick »

zzzcpan wrote: post #22
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.

Built-in implementations usually are kind of slow, waste memory, have broken iterators [1], even in modern languages. If either of those things are important - it's better to do some research and maybe even invent your own. [1] when you can't both iterate and insert items consistently in the same loop

"Usually", really? Which languages are you thinking of, and have you benchmarked them?

Re: Diving into the world of hash tables

#48

Post by [deleted] »

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…

[deleted]

Re: Diving into the world of hash tables

#50

Post by obstinate »

lsadam0 wrote: post #37
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.

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 terrible for performance, and that's a big part of why Python is slow.

But how are other languages fast? Doesn't every language have to resolve variable names to memory locations? Well, yes, but fast languages do this mostly at compile time. How? Well, I'm not an expert in this, but at a high level, each variable is assigned a location in memory or registers, and then future references to that variable are rewritten to refer to the memory location by register name or memory address. This takes the whole "looking up a name" issue out of the path of work that has to get done at runtime. And you've switched from looking up things in tables to operating directly on registers and memory locations.

BTW, this has nothing to do with high-versus-low level. It's more about how mutable the process of name resolution is after program compilation. One could theoretically write an assembly language where memory locations are names, not numbers. If reflective features like runtime scope editing are available, this would be a very low-level language that still requires some kind of dictionary lookup at runtime.

Post reply on HN