4 ms·

One trick I learned from https://craftinginterpreters.com/hash-tables.html https://craftinginterpreters.com/hash-tables.html is that you don't need an extra lin

One trick I learned from https://craftinginterpreters.com/hash-tables.html https://craftinginterpreters.com/hash-tables.html is that you don't need an extra linked list for each bucket... But how do you handle collisions then ? The trick is that you make sure that your table is large enough to not have a lot of collisions, then if you have a collision instead of storing exactly in the bucket given by the hash, you store it in the next available bucket. When you look for a key, you get the hash, then the index from the hash, and you start searching at this point. If you reach an empty value, then there is no value. If you find the value then you return that. So everything is stored in a single array, no need for extra allocations and it is better for cache locality. The same principle is used here for very minimal hash table (13 lines): https://nullprogram.com/blog/2020/10/19/ https://nullprogram.com/blog/2020/10/19/ This video also talk about how to optimize hash table and look into several implementations: https://www.youtube.com/watch?v=DMQ_HcNSOAI&t=1690s&ab_channel=strager https://www.youtube.com/watch?v=DMQ_HcNSOAI&t=1690s&ab_chann... . It talks about techniques used by advanced hash table. There was a lot more that I didn't know.

masklinn 3y ago
That’s not really a trick? It’s an open addressing hash table (https://en.wikipedia.org/wiki/Open_addressing https://en.wikipedia.org/wiki/Open_addressing), with a linear probing collision resolution (https://en.wikipedia.org/wiki/Linear_probing https://en.wikipedia.org/wiki/Linear_probing).
- scrozart 3y ago
  Yup. This is how they're taught in CS undergrad (as of 10 years ago, anyway).
  - tomgp 3y ago
    And 25 years ago :D (though we did the linked list implementation too)
  - sureglymop 3y ago
    This is how it was taught to me in a CS undergrad class last week. What we didn't look at though was, what happens when the hash table is full? Does everything get rehashed into a bigger table? What are the Performance implications of that? I wish it would have gone just a little further.
    - masklinn 3y ago
      > Does everything get rehashed into a bigger table? Usually yes, though it’s also possible to perform gradual resizing that’s less efficient so it’s only used when needed (e.g. real time systems which can’t afford a full resize). > What are the Performance implications of that? Same as a vector. That’s why hashmaps generally provide an amortized insertion time. > What we didn't look at though was, what happens when the hash table is full? Of note: a hash table never gets full, hash tables have a load factor (which mostly depends on the collision resolution algorithm, as that informs how performances degrade as collisions increase), and the table will resize when it exceeds its load factor, to maintain a “healthy” rate of collisions.
    - jlokier 3y ago
      Even before it's full, an open addressing hash table (also called closed hashing - confusing names!) becomes very slow as it gets close to full, because most of the table needs to be scanned on inserts, and on queries for the recently inserted vales. When it's full, insertion requires rehashing into a bigger table. (Or you can use an overflow list when the table is full or nearly full, if you don't want to rehash and prefer to treat this case as rare and ok to be slow.) So for a general purpose open addressing / closed hashing hash table where you don't know the number of items in advance, rehashing to a bigger table is done at some threshold before it's actually full. As long as you do rehashing using a multiplier, for example doubling the size at 50% full (as opposed to adding a fixed amount to the size), it stays fast on average, but the rehashing operations are of course individually slow. They just don't happen often, so the average stays at O(1) time. This is called amortised O(1) time complexity. The ideal threshold for resizing depends on the probing type. Linked list hash tables, (also called closed addressing or open hashing - I think linked list is a clearer name) don't suffer from catastrophic slowdown with size in the same way as the open addressing / closed hashing type. Nor abrupt failure when full, because they're never full. These can still be resized and this is required if O(1) time is required to arbitrary numbers of items, but the resizing threshold is not as critical. If not resized they gradually degrade to O(N) time performance when filled too much. Many applications use fixed size linked list hash tables safely because of this. Array-of-arrays hash tables behave similarly to linked list hash tables.

masklinn 3y ago

That’s not really a trick? It’s an open addressing hash table (https://en.wikipedia.org/wiki/Open_addressing https://en.wikipedia.org/wiki/Open_addressing), with a linear probing collision resolution (https://en.wikipedia.org/wiki/Linear_probing https://en.wikipedia.org/wiki/Linear_probing).

scrozart 3y ago
Yup. This is how they're taught in CS undergrad (as of 10 years ago, anyway).
- tomgp 3y ago
  And 25 years ago :D (though we did the linked list implementation too)
- sureglymop 3y ago
  This is how it was taught to me in a CS undergrad class last week. What we didn't look at though was, what happens when the hash table is full? Does everything get rehashed into a bigger table? What are the Performance implications of that? I wish it would have gone just a little further.
  - masklinn 3y ago
    > Does everything get rehashed into a bigger table? Usually yes, though it’s also possible to perform gradual resizing that’s less efficient so it’s only used when needed (e.g. real time systems which can’t afford a full resize). > What are the Performance implications of that? Same as a vector. That’s why hashmaps generally provide an amortized insertion time. > What we didn't look at though was, what happens when the hash table is full? Of note: a hash table never gets full, hash tables have a load factor (which mostly depends on the collision resolution algorithm, as that informs how performances degrade as collisions increase), and the table will resize when it exceeds its load factor, to maintain a “healthy” rate of collisions.
  - jlokier 3y ago
    Even before it's full, an open addressing hash table (also called closed hashing - confusing names!) becomes very slow as it gets close to full, because most of the table needs to be scanned on inserts, and on queries for the recently inserted vales. When it's full, insertion requires rehashing into a bigger table. (Or you can use an overflow list when the table is full or nearly full, if you don't want to rehash and prefer to treat this case as rare and ok to be slow.) So for a general purpose open addressing / closed hashing hash table where you don't know the number of items in advance, rehashing to a bigger table is done at some threshold before it's actually full. As long as you do rehashing using a multiplier, for example doubling the size at 50% full (as opposed to adding a fixed amount to the size), it stays fast on average, but the rehashing operations are of course individually slow. They just don't happen often, so the average stays at O(1) time. This is called amortised O(1) time complexity. The ideal threshold for resizing depends on the probing type. Linked list hash tables, (also called closed addressing or open hashing - I think linked list is a clearer name) don't suffer from catastrophic slowdown with size in the same way as the open addressing / closed hashing type. Nor abrupt failure when full, because they're never full. These can still be resized and this is required if O(1) time is required to arbitrary numbers of items, but the resizing threshold is not as critical. If not resized they gradually degrade to O(N) time performance when filled too much. Many applications use fixed size linked list hash tables safely because of this. Array-of-arrays hash tables behave similarly to linked list hash tables.