Live data from Hacker News

Diving into the world of hash tables

zeroequalsfalse.press

21–30 of 107 posts

Re: Diving into the world of hash tables

#21
post #18
post #10

Earlier quoted context omitted.

Sets are just like hashes where the value is always "true" for each key.

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"

Re: Diving into the world of hash tables

#22
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

Re: Diving into the world of hash tables

#23
post #10

Earlier quoted context omitted.

Sets are just like hashes where the value is always "true" for each key.

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?

Re: Diving into the world of hash tables

#24
This is one of those data structures that everyone should try building at least once, kind of like linked lists, etc. Semi-unrelated, I built a couple of toy implementations a few years ago using the same basic ideas:

* This one is the my original written in something halfway resembling scheme: https://github.com/arlaneenalra/Bootstrap-Scheme/blob/master...

* And this implementation is part of a half finished byte code scheme that I haven't touched in a few years. Another project I need to get back to. Interface: https://github.com/arlaneenalra/insomniac/blob/master/src/in... Internals: https://github.com/arlaneenalra/insomniac/tree/master/src/li...

They were kind of fun to build and I'd recommend giving, especially if you have some skill but don't think you have the chops. To get a working toy isn't really all that hard once you understand the principals.

Re: Diving into the world of hash tables

#25
post #16
post #6

It's actually sets that are underrated. All languages should come with a reference implementation. Hashtables aka Maps aka Dictionaries aka Associative arrays are just fine.

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…

Yes, while a set can be derived or mimicked if you have a hashtable for example, I'm specifically referring to all the common set operations you'd typically want to have.

Using a map/hashtable as a set is just the tip of the iceberg.

In many cases you don't need a key and a value and you can get rid of a lot of loopy and complicated code if you had a simple set to utilize with its useful operations.

Re: Diving into the world of hash tables

#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 implementations is to keep a sorted vector of keys and a respective vector of values. There's loki::assocvector, booost::flat_unordered_map that do this for instance. Now insertion is slow, but iteration and retrieval are very fast (a fast O(logn) by binary search with few cache misses). It's also memory efficient, since no pointers between elements.

If you have one big dictionary you would use throughout an application, and know the data up front, 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. Now you have a memory efficient and extremely fast dictionary data structure.

One other strategy any intermediate coder can implement is to have two unsorted coindexed arrays. You don't even need a hash function for this. Now iterating and insertion through the table is extremely fast, and it is memory efficient, but finding a key is just a fast O(n). So this is good for smaller tables. In C++ you could implement it as a std::pair, vector>. If you need a quick small map in a function this is often the fastest data structure you can implement without too many headaches.

Re: Diving into the world of hash tables

#27
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. 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?

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

Re: Diving into the world of hash tables

#28
post #10

Earlier quoted context omitted.

Sets are just like hashes where the value is always "true" for each key.

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 .

This exactly, I hear over and over: just use a hashtable...totally misses the point.

Re: Diving into the world of hash tables

#29
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 tuple, and returning hash(self.a, self.b, ...). [1]

Java takes a simmilar approach, but does not make an explicit recomandation on how to implement hashCode(). In my experience, most programmers just XOR the hash of the fields, which (depending on the object) could be very sub-optimal, but is often good enough. Based on the doc, the typical implementation for Object.hashCode is to just take the memory address of the object.

[0] https://docs.python.org/3/reference/datamodel.html#object.__...

[1] Pythons tuple hash function may be found here: https://hg.python.org/cpython/file/dcced3bd22fe/Objects/tupl...

[2] https://docs.oracle.com/javase/7/docs/api/java/lang/Object.h...

Re: Diving into the world of hash tables

#30
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!

Good question! Yes. Here’s an example: http://cyan4973.github.io/xxHash/
Post reply on HN