3 ms·
I think they address this in the article. They use arrays instead of linked lists. Which makes direct key comparison very fast, because it's all in CPU cache.
by bufferoverflow 2y ago
I think they address this in the article. They use arrays instead of linked lists. Which makes direct key comparison very fast, because it's all in CPU cache.
- tialaramex 2y ago"I just use an array" doesn't solve the problem "What if the array is full?". In fact it makes that problem acute. A linked list structure will degrade gradually as we shove more entries with the same hash into it, every look-up incurs a pointer chase down the entire list, slower is eventually unacceptable but we do get signs first -- but with arrays we're just screwed, in C it's pretty likely we end up with an illegal dereference or we lose data once there's no room.
- mst 2y agoIf it's designed to be used for caching, then replacing an old entry or throwing away the new one is quite possibly a perfectly reasonable "out." If it's designed to be used for other purposes as well, not so much. (I wasn't entirely sure which from reading the article)