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`?
Diving into the world of hash tables
21–30 of 107 posts
Re: Diving into the world of hash tables
#22It 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.
[1] when you can't both iterate and insert items consistently in the same loop
Re: Diving into the world of hash tables
#23Earlier 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 .
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 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
#25It'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…
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
#26For 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
#27Earlier 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?
Re: Diving into the world of hash tables
#28Earlier 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 .
Re: Diving into the world of hash tables
#29Quick 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!
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
#30Quick 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!