The dict/hash implementation in K (since 1993 or so ..) is much simpler, cleaner, takes much less memory and often faster - though speed depends on the actual u

The dict/hash implementation in K (since 1993 or so ..) is much simpler, cleaner, takes much less memory and often faster - though speed depends on the actual use case more than anything. The idea is that instead of the hash map being a list of <key,value> items indexed by key, there's a vector of keys, a vector of values (with matching indices), and a search index (usually a hash, but could be a tree) that maps a key to the index; note that the search index does not need a copy of the key even if it is inexact because one can always refer to the keys vector. The cons: * You can't pass a single <key,value> object without building one * You may incur twice or thrice cache loads (one for index, one for key, and if correct, one for value) whereas on a conventional <key, value> list, they are likely to be on the same cache line. * (edit: added based on aidenn0 comment, see discussion below): Removal is generally O(n) unless you are willing to give up one of the pros; but even if you give some up, it's still usually more featureful than commonly used implementations. The pros: * Insertion order is preserved - OrderedDict for free! * Getting the list of keys, or the list of values, e.g. python's keys() and values() methods, are O(1) and allocation free * Applying a function to each item needs to allocate a new value vector, but can reuse the key vector -- and if the function doesn't need the key, you don't actually have to fetch it - e.g., to normalize a map so values sum to 1, you can do: whole = sum(mymap.values()) normalized = apply_values(mymap, lambda x: x/whole) And get a normalized map with the same keys and literally the minimal number of allocations and operations possible for a concrete datatype * Specialization is by the key type, regardless of the value type - which means that a few efficient implementations (for ints, longs, floats, strings, symbols) manage to often provide C++ speeds for an interpreted language. * Memory packing is about as tight as it can be. Your key is a double, and your value is one byte? You pay exactly 9 bytes per record + index size (which, e.g. for a 30,000 record map, takes two bytes per hash slot, or ~128KB for a 64K slot table). This is true whether you are running on an 16-bit, 32-bit, 64-bit or 128-bit processor. * It is straightforward and natural to implement with almost no pointers involved, meaning that it is trivial to share memory among processes (at least for read only accesses) and to use with memory-mapped storage -- to the point that you can have an 8GB dictionary which is instantly mmap()/MapViewOfFile()d into existence, and is no different in any way than any other one - you pay disk access for the records you use, but enjoy OS cache/page management, with cache shared between processes and between subsequent runs -- no need to special case this dictionary just because it's big. The Python 3.6 implementation switched from a hash-indexed <hash,key,value> vector to a <hash -> order> and ordered <key,value> vector, and saw speed improvements and memory use reductions. Due to Python's legacy and structure, they could not have gone farther on the K way, except for CPU cache effects. Having used APL and K for over 15 years now, I find it weird seeing the same Smalltalk-inspired hash table structure come up in every single new runtime and language implementation.