16 ms·
Diving into the world of hash tables
- spankalee 9y agoI wonder how hash tables are "underrated". They're probably _the_ data structure, if there is one.
- sjroot 9y ago"An underrated data structure" Uh......
- hprotagonist 9y ago"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!" @_@
- whatshisface 9y agoPython has its own very cleverly optimized dict implementation: http://pybites.blogspot.com/2008/10/pure-python-dictionary-implementation.html http://pybites.blogspot.com/2008/10/pure-python-dictionary-i...
- hprotagonist 9y agohettinger's updates at pycon this year: it's better! https://www.youtube.com/watch?v=npw4s1QTmPg https://www.youtube.com/watch?v=npw4s1QTmPg
- dom0 9y agoPython (and Ruby and some others) form the category of hash table interpreters—since most things are hash tables.
- draw_down 9y agoI like both kinds of data structures- maps and lists. (Just kidding, list is but a degenerate case of map)
- mabbo 9y agoI 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.
- shishy 9y agoThe 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.
- iainmerrick 9y agoYeah, that's a weird title! I assumed it must be the actual title of the post, but no.
- lsadam0 9y agoReally. Hash tables are one of my most used data structures.
- obstinate 9y agoIn 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.
- deckarep 9y agoIt'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.
- xyzzy4 9y agoSets are just like hashes where the value is always "true" for each key.
- mcpherrinm 9y agoWhile 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<T> to use less space than Map<T, bool>.
- slig 9y ago> 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?
- douche 9y agoBecause it is JavaScript, and there's some kind of unspoken rule about not doing things properly and instead releasing broken things.
- floogtheunfound 9y agoI’m shocked this isn’t being aggressively down voted...oh wait... it’s bashing js and not bashing haskell...nvm
- TheAceOfHearts 9y ago
- rdtsc 9y agoIt 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.
- zzzcpan 9y agoBuilt-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
- iainmerrick 9y ago"Usually", really? Which languages are you thinking of, and have you benchmarked them?
- flukus 9y agoIt's often true due to a few factors. One is that they are safe, whereas a specific use case may not need the same level of safety. They generally optimize for the general case as well, but in your own code you can optimize for the very specific use case you have. One I ran into many years ago was implementing my own singly linked list by adding the next pointer to another piece of data. In this one specific case it was worth removing another layer of indirection. I was still young though, so there were probably even better ways of handling it. I have only encountered these scenarios a small handful of times, but I'm not a very low level developer.
- dom0 9y ago> And just use the built-in ones don't invent your own unless there is a very good reason for it. Uhm, hash tables are one of these things where plenty can be gained by tailoring the structure to the application. It's not a one-size-fits-all, and it's not nearly as easy as it would seem to make a good general-purpose HT.
- fenomas 9y agoMods, 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.
- OJFord 9y agoThough, in this case, changing it from the original does seem warranted. (This was just another bad choice...)
- iainmerrick 9y agoWhat's wrong with leaving it unchanged? The blog post title seems fine.
- pvg 9y agoYou can mail the mods and ask them, they usually fix these fairly quickly.
- booleandilemma 9y ago"They didn't teach me about these in my coding bootcamp"
- taeric 9y agoHash Table has basically been elevated to a general idea lately. Pretty much anyone that is looking for an association between keys and values is using what they will call a hash table. To that end, few people actually know anything about how they are implemented. (And apologies if this comes across as negative, I do not mean it as a value judgement.) This was different back when you would pick something like an alist to store associations. There the implementation stared you in the face. Same for the times you had to implement your own hash table. I don't exactly yearn for those days. Though, I am curious if alists actually win in speed for a large number of smaller hash tables.
- yxhuvud 9y agoDepends on implementations of the alist and of the hash table. It is even fully possible that the small hash table will use an alist for the cases with few (and small) elements.
- taeric 9y agoFair. I was making a huge assumption that the alist would be implemented as you statically see it in code. My point was supposed to be that an alist really has an obvious implementation, whereas a hashtable actually does not. My main objection being that there is a ton of glossing over what goes into an actual hashtable. While I would expect someone to be able to do a basic alist implementation, I have grown away from expecting folks to do a basic hash table.
- mhh__ 9y agowtf i love hash tables now! ;)
- deleted 9y ago[deleted]
- Cyph0n 9y agoQuick 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!
- gizmo686 9y agoIn 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.__hash__ 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/tupleobject.c https://hg.python.org/cpython/file/dcced3bd22fe/Objects/tupl... [2] https://docs.oracle.com/javase/7/docs/api/java/lang/Object.html#hashCode() https://docs.oracle.com/javase/7/docs/api/java/lang/Object.h...
- jwilk 9y agoPython has migrated from hg to git. The current version of tupleobject.c is here: https://github.com/python/cpython/blob/master/Objects/tupleobject.c https://github.com/python/cpython/blob/master/Objects/tupleo...
- splicer 9y agoGood question! Yes. Here’s an example: http://cyan4973.github.io/xxHash/ http://cyan4973.github.io/xxHash/
- emeraldd 9y agoThis 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/lib/hash.scm 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/include/hash.h https://github.com/arlaneenalra/insomniac/blob/master/src/in... Internals: https://github.com/arlaneenalra/insomniac/tree/master/src/libinsomniac_hash 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.
- VHRanger 9y agoIf 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<key>, vector<value>>. If you need a quick small map in a function this is often the fastest data structure you can implement without too many headaches.
- YZF 9y agoYou 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).
- VHRanger 9y agoI mean insertion into the dictionary in general.
- obstinate 9y agoI 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.
- relics443 9y agoMy data structures professor made a habit of proclaiming every few classes: "Give me a hash table, and I could rule the world"
- deleted 9y ago[deleted]
- afinlayson 9y agoI think 90% of technical interview questions result in hashtable in it. underrated wouldn't be the word I'd use.
- Izmaki 9y agoNo they're not. And if they are, they are more advanced than this brief overview.
- skybrian 9y agoThis article explains "2-Level Hashing" which is apparently "dynamic perfect hashing." While interesting, I'm wondering how much it's actually used? Or is it just of theoretical interest? [1] https://en.wikipedia.org/wiki/Dynamic_perfect_hashing https://en.wikipedia.org/wiki/Dynamic_perfect_hashing
- ribs 9y agoThis word "extremely" has me skeptical from sentence one. Maybe I'm jaded.