23 ms·

Undergraduate shows that searches within hash tables can be much faster

1304 points by Jhsto 2y ago

varjag 2y ago
tl;dr sublinear worst case query and insertion in hash tables.
- bean-weevil 2y ago
  Specifically, (log x)^2
- pinoy420 2y ago
  Eli5?
  - laweijfmvo 2y ago
    hash tables are most famous for their O(1) lookup time, but then you have to deal with collisions. There's many famous ways of dealing with collisions and you can convince yourself of their [worst case] lookup time. The article is discussing a new upper bound on that worst case.
    - SilasX 2y ago
      This is always a point of frustration for me. Under the normal big-O model, hashtables aren't, and can't be O(1) lookup, even for the mythic perfect hash function! You can only get the O(1) figure by breaking the big-O model and bolting on some in-practice assumptions[1] that are used nowhere else in discussion of asymptotic complexity. Specifically, as you resize the table, you need a function with a bigger output space to give you more places to store the item. To have a bigger output space, you unavoidably have to do more computations. If you go from a function with n possible outputs to one with 2n possible outputs, as n goes to infinity, you eventually have to use a function with more steps. [1] elaborated on in this earlier discussion: https://news.ycombinator.com/item?id=9807739 https://news.ycombinator.com/item?id=9807739 Specifically this comment about the extra assumptions: https://news.ycombinator.com/item?id=9813524 https://news.ycombinator.com/item?id=9813524
      - Aunche 2y ago
        To be fair, in tree tables, we also assume that comparison is a constant time operation as well when it also necessarily needs to be O(log(n)) for an arbitrary sized table, making it an O(log(n)^2) data structure by this standard.
        meribold 2y ago
        You don't need to compare the whole key most of the time. I think the amortized cost for a comparison is in O(1).
        sltkr 2y ago
        Not in a balanced tree, since the further down the tree you go, the longer the shared prefix between the search key and node key becomes. So the complexity becomes something like 1 + 2 + 3 + .. + log n = O(log^2 n).
        meribold 2y ago
        Good point. Perhaps we could store the length of the common prefix from the last time we went left as well as from the last time we went right. The minimum of those two should remain a common prefix with the search key for the rest of the lookup and should therefore be safe to skip during subsequent comparisons.
        SilasX 2y ago
        But that would actually help it because you can store how far down the match is by that point in the tree, and know how few digits you have to actually compare.
      - magicalhippo 2y ago
        Your sense of frustration seems to stem from thinking about something which is similar to big-O, but not actually being big-O. All of the points you raise are valid if you want to have a good understanding of actual runtime cost of an algorithm. None of it is relevant if you want to compare algorithms according to big-O, in order to find one which doesn't lead to failure[1] when faced with large amounts of data. Perhaps you should define your own big-R notation for what you're after. [1]: https://arstechnica.com/information-technology/2013/12/exponential-algorithm-making-windows-xp-miserable-could-be-fixed/ https://arstechnica.com/information-technology/2013/12/expon...
    - anothernewdude 2y ago
      O(1) lookup is bullshit that ignores the memory hierarchy.
  - tejohnso 2y ago
    If you're trying to find an available cubby hole for your boots, you'll find one very quickly if they're almost all empty. But if they're almost all full, it will take longer for you find one. This discovery shows that it won't take as long as previously thought.
sam0x17 2y ago
This is huge, when can we get a rust implementation?
- natpalmer1776 2y ago
  Be the change you want to see in the world!
- maujim 2y ago
  claude one-shot it, then open source it, and build from there
  - DC-3 2y ago
    Sounds like a really good way to get a robust implementation of a fiddly and novel algorithm.
duskwuff 2y ago
Paper: https://arxiv.org/pdf/2111.12800 https://arxiv.org/pdf/2111.12800
- something98 2y ago
  This is the correct (2025) paper. https://arxiv.org/abs/2501.02305 https://arxiv.org/abs/2501.02305
qntty 2y ago
A cool result, but it seems like it should be called a computer science conjecture
- ayhanfuat 2y ago
  Especially considering “data science” is nowhere near 40 years old.
  - Tetraslam 2y ago
    https://www.rcseng.ac.uk/library-and-publications/library/blog/mapping-disease-john-snow-and-cholera/ https://www.rcseng.ac.uk/library-and-publications/library/bl...
  - anthk 2y ago
    Statistics are old.
    - speed_spread 2y ago
      On average.
      - lupire 2y ago
        Probably not. Most statistics is new, due to the explosion of interest since the advent of computers.
- frabert 2y ago
  I think the article's author may have seen the cs.DS classification on the arxiv and assumed it meant Data Science instead of Data Structures
  - nerdponx 2y ago
    It's also possible that they don't actually know the difference, or was even asked to change it by an editor to make it sound more trendy. Skepticism of even good journalism is healthy. Gell-Mann amnesia and all.
jjallen 2y ago
Is it just me or did the article not go in to how the improvement works, just the speed of it?
- pinoy420 2y ago
  It didn’t really go in to either. It doesn’t have any sort of benchmarking or any best/worst case fits?
  - Ar-Curunir 2y ago
    This is a theory of CS paper. The algorithm might not even be implementable.
- jjallen 2y ago
  I was very interested in the improvement. That is the crux of the subject if you ask me.
- reportgunner 2y ago
  Yeah usually when article starts by explaining what is known or tells you a story they do it to fluff up the text and bait you into reading because the actual content you want is not there.
amazingamazing 2y ago
This is a good test because it’s recent. Let’s see if deep research can come up with this result without just copying this. Edit: gpt4, Gemini 2 and Claude had no luck. Human driven computer science is still safe.
- rvz 2y ago
  Original thought or additional intuitive improvements such as this discovery is what we should be looking for. This can come from anywhere in the world. The best part is, it did NOT discovered from an AI program.
  - azinman2 2y ago
    And yet those who want AGI often talk about the potential for AI to solve all our major problems.
  - ANighRaisin 2y ago
    It would be better if it came from AI, as it would show that AI will be able to make helpful improvements to technology. AI has come up with impartments to other algorithms, such as matrix multiplication, so it's not super farfetched for it to come up with something similar to this, especially with all the improvements to AI lately. So much pessimism about AI...
- itishappy 2y ago
  Do you think the results would be different if you tried this with, say, a cohort of PhD students?
- refulgentis 2y ago
  I'm so confused trying to imagine exactly what you prompted. What did you prompt?!
  - amazingamazing 2y ago
    I told it is was possible, the worst case runtime characteristics and asked it to figure out how you would achieve it. I also gave it some hints from the paper.
orlp 2y ago
Skimming the paper [1], the key difference they used is that their hash table insertion algorithm will probe further than the first empty slot, instead of greedily filling the first empty slot it finds. They combine this with a clever probing sequence which provably finds empty slots efficiently, even if the table is very full. This means insertions when the hash table is less full are slower, but you avoid the worst-case scenario where you're probing for the last (few) remaining open slot(s) without any idea as to where they are. [1]: https://arxiv.org/pdf/2501.02305 https://arxiv.org/pdf/2501.02305 --- An interesting theoretical result but I would expect the current 'trick' of simply allocating a larger table than necessary to be the superior solution in practice. For example, Rust's hashbrown intentionally leaves 1/8th (12.5%) of the table empty, which does cost a bit more memory but makes insertions/lookups very fast with high probability.
- SiempreViernes 2y ago
  But you could do some hybrid, where you do greedy fill for a while and then switch to this fancier fill once your table is approaching full (using some heuristic)?
  - gizmo 2y ago
    Not really because you have to use the same algorithms during subsequent lookups. Imagine you add a bunch of items with insert algorithm A, then you cross some threshold and you insert some more items with Algorithm B. Then you delete (tombstone) a bunch of items. Now you look up an item, and the slot is filled, and you're stuck. You have to proceed your lookup with both algorithms to find what you're looking for (thereby giving up any performance benefits) because the current occupancy doesn't tell you anything about the occupancy at the time when the item you were looking for was inserted.
  - layer8 2y ago
    I would assume that you need to start early to be able to reap the benefits once the table is almost full.
  - DevelopingElk 2y ago
joe_the_user 2y ago
The theoretical properties of hash table always seemed so impressive to me that they bordered on magic (and this just extends them). What seemed crazy was how they could be so much better than trees, which to me were intuitively the most efficient way to store data. What I realized is that the theory of hash tables involves a fixed-sized collection of objects. For this fixed collection, you create a hash-function and used that like a vector-index and store the collection in a (pre-allocated) vector. This gives a (fuzzy-lens'd) recipe for O(1) time insert, deletion and look-up. (The various tree structures, in contrast, don't assume a particular size). The two problems are you have to decide size beforehand and if your vector gets close to full, you insert etc processes might bog-down. So scanning the article, it seems this is a solution to the bogging down part - it allows quick insertion to a nearly-full table. It seems interesting and clever but actually not a great practical advance. In practice, rather than worrying a clever way to fill the table, I'd assume you just increase your assumed size. Edit: I'm posting partly to test my understanding, so feel to correct me if I'm not getting something.
- vessenes 2y ago
  It looks to me like the idea is, as you generally describe, that you segment your table into a 2d structure (well conceptually) and proceed to fill one ‘row’ at a time until it’s about 75% full, at which point you move on to the next one. I don’t have time to fully grok the paper, but they claim this makes insertion consistently fast (I believe this until we’re at 75% of total capacity, but maybe they have some other mode for filling when they’re at 75% in every row?). They also claim retrieval is fast, and I didn’t read enough to understand how even retrieval works, or why it is faster. I’ll put out that there a lot of times that it would be really nice to have a nearly full hash table still, you know, work. You can’t always change the size of one during execution of a program. And, in some environments memory counts a lot. That said, I would like to see and play with an implementation — I’m not sure this is ‘worth it’ in the general case. It is also probably cache inefficient, as are most things about hash tables, with the exception of linear probing for reading out of a fairly full one, in which case, you get to just keep pulling stuff directly out of memory to check it. So, it’s not clear to me that this is performance wise worth it. Anyway, I’d like to fully understand it, it seems like an interesting new idea.
MR4D 2y ago
Reading through this article is like reading a description of the Monty-Hall problem. [0] It's as through the conclusion seems to defy common sense, yet is provable. [1] [0] - https://priceonomics.com/the-time-everyone-corrected-the-worlds-smartest/ https://priceonomics.com/the-time-everyone-corrected-the-wor... [1] - 2nd to the last paragraph: "The fact that you can achieve a constant average query time, regardless of the hash table’s fullness, was wholly unexpected — even to the authors themselves."
- darknavi 2y ago
  I always really enjoyed the Numb3rs lecture on Monty-Hall https://www.youtube.com/watch?v=P9WFKmLK0dc https://www.youtube.com/watch?v=P9WFKmLK0dc
- ryao 2y ago
  > “Our brains are just not wired to do probability problems very well, so I’m not surprised there were mistakes,” Stanford stats professor Persi Diaconis told a reporter, years ago. “[But] the strict argument would be that the question cannot be answered without knowing the motivation of the host.” This is wrong. Let’s label the goats A and B to simplify things (so we do not need to consider the positions of the doors). There are 3 cases: 1. You pick the right door. The other two doors have goats. The host may only choose a goat. Whether it is A or B does not matter. 2. You pick the door with goat A. The host may only choose goat B. 3. You pick the door with goat B. The host may only choose goat A. The host’s intentions are irrelevant as far as the probability is concerned (unless the host is allowed to tell the contestant which door is correct, but I am not aware of that ever being the case). 2/3 of the time, you pick the wrong door. In each of those cases, the remaining door is correct. The most strict argument is yet another statistics professor got basic statistics wrong.
  - CrazyStat 2y ago
    I can assure you Diaconis didn’t get it wrong. > "The problem is not well-formed," Mr. Gardner said, "unless it makes clear that the host must always open an empty door and offer the switch. Otherwise, if the host is malevolent, he may open another door only when it's to his advantage to let the player switch, and the probability of being right by switching could be as low as zero." Mr. Gardner said the ambiguity could be eliminated if the host promised ahead of time to open another door and then offer a switch. The hosts’s intentions absolutely do matter, because the problem (as originally stated) doesn’t specify that the host always opens a door and offers a switch. Maybe he only offers a trade when you initially picked the good door.
ascorbic 2y ago
And they wouldn't make him first named author on the paper
- yacin 2y ago
  it's common in math/cs theory papers to have the order of authors be alphabetical rather than in descending order of contribution.
  - writebetterc 2y ago
    Good, but that can also be noted in a subtitle right below the authors (I've seen this in papers myself!)
    - Ar-Curunir 2y ago
      The paper is not targeted at laymen, but other members of the research community, who are aware of the author ordering convention.
  - mometsi 2y ago
    I wonder if there's a significant nominative determinism effect-- One might expect some of the most prominent people in math and cs theory to have names like Aaronson and Baez...
    - chikere232 2y ago
      It would be most fair to hash the names first, especially for this paper
      - usefulcat 2y ago
        I suppose then the next question will be which author gets to choose the hash function..
        2y ago
default-kramer 2y ago
> And for this new hash table, the time required for worst-case queries and insertions is proportional to (log x)2 — far faster than x. > The team’s results may not lead to any immediate applications I don't understand why it wouldn't lead to immediate applications. Is this a situation where analysis of real-world use cases allows you to tune your hash implementation better than what a purely mathematical approach would get you?
- jeffbee 2y ago
  Complexity analysis and actual systems programming have been diverging for a while. I don't see anything in the paper that will inform practice.
  - naasking 2y ago
    How so?
    - zamadatix 2y ago
      Even when something isn't a galactic algorithm "how well it maps to being done efficiently in real hardware with hardware sized data sizes" is more and more often the important bit over "slightly better bounds at infinity". The former is probing the edge of mathematics while the latter is probing the edges of practical construction so they rarely seem to align much anymore at these depths.
      - gauge_field 2y ago
        A contributing factor is how complex/smart the current hardware is. It can have cache line size, different forms of hardware/software prefetching, different ports for different ops, memory latency, simd extensions. These leave many opportunities for algorithms to be optimized over. There is also the issue of real life scenarios not matching with asymptotic ones (due to e.g., size of input), which when coupled with previous factors, leads to even more potential optimization schemes. Obligatory reference: https://agner.org/optimize/ https://agner.org/optimize/
brink 2y ago
Krapivin made this breakthrough by being unaware of Yao's conjecture. The developer of Balatro made an award winning deck builder game by not being aware of existing deck builders. I'm beginning to think that the best way to approach a problem is by either not being aware of or disregarding most of the similar efforts that came before. This makes me kind of sad, because the current world is so interconnected, that we rarely see such novelty with their tendency to "fall in the rut of thought" of those that came before. The internet is great, but it also homogenizes the world of thought, and that kind of sucks.
- aidenn0 2y ago
  > I'm beginning to think that the best way to approach a problem is by either not being aware of or disregarding most of the similar efforts that came before. This makes me kind of sad, because the current world is so interconnected, that we rarely see such novelty with their tendency to "fall in the rut of thought" of those that came before. The internet is great, but it also homogenizes the world of thought, and that kind of sucks. I think this is true only if there is a novel solution that is in a drastically different direction than similar efforts that came before. Most of the time when you ignore previous successful efforts, you end up resowing non-fertile ground.
  - layman51 2y ago
    Right, the other side is when you end up with rediscoveries of the same ideas. The example that comes to my mind is when a medical researcher found the trapezoidal rule for integration again[1]. [1]: https://fliptomato.wordpress.com/2007/03/19/medical-researcher-discovers-integration-gets-75-citations/ https://fliptomato.wordpress.com/2007/03/19/medical-research...
    - sitkack 2y ago
      I think that shows how great the trapezoidal rule is. I feel like this is brought out too many times, that now it is used to make fun of people. It is 18 years old at this point.
ryao 2y ago
<deleted>
- j-scott 2y ago
  I think this was meant as a reply to https://news.ycombinator.com/item?id=43004919 https://news.ycombinator.com/item?id=43004919
  - deleted 2y ago
    [deleted]
dooglius 2y ago
It looks like the result only matters in the case where the hash table is close to full. But couldn't one just deal with this case by making the table size 10% bigger? (Or, if it is resizeable, resizing earlier)
- nhumrich 2y ago
  Yes, which is what most real world hash tables do. They resize themselves once hash collision is too probable.
- xxs 2y ago
  In reality 75% is the standard fill factor for linear probe that also exhibits the best locality (if the table gets too full it just allocated double (or x) the memory, and copies the existing entries). Most non-linear probe tables (e.g. cookoo) suffer due to the fact RAM is not 'random' at all.
quantum2022 2y ago
This is neat! I always wondered if there would be a way to 'containerize' tables like this. IE a regular table is like a bulk carrier ship, with everything stuffed into it. If you could better organize it like a container ship, you could carry much more stuff more efficiently (and offload it faster too!)
- doublerabbit 2y ago
  Easy stuff. Convert table row to a string, json to whatever Apply base16 to the that variable You've now got a base16 string of that data. Create a hash table, setup a key value for that base16 string. You now have a container holding the data. All you need to do is decode the hex string and you've got base32 data.
  - internetter 2y ago
    What you just described is magnitudes slower than even conventional hash tables
    - doublerabbit 2y ago
      I'd like to see your solution.
      - internetter 2y ago
        My solution would be a conventional hash table. Now, I will consider using the solution defined in the paper.
        doublerabbit 2y ago
        Yeah? Not for me. I prefer my way of things. More fun and learning.
  - deleted 2y ago
    [deleted]
trebligdivad 2y ago
Anyone got a simple implementation of 'Tiny pointers'? My mind prefers code/pseudo-code first rather than the proof.
zombiwoof 2y ago
Take that AI :)
jimnotgym 2y ago
Now we have faster data structures we can fill that extra time by writing less efficient code, and loading more pointless libraries. This is the march of computer science.
nickhodge 2y ago
I bet this guy would still fail a first round FAANG developer interview requiring a Hash Table solution to move on in the process. "Yeah, sorry. You didn't use the right Hash Table"
- rswail 2y ago
  Which is exactly the difference between "programming" and "computer science".
  - justanotherjoe 2y ago
    Oh, come on. Anyone can use a hash table. What this man did is not even comparable to that.
ChrisMarshallNY 2y ago
As the villain in Scooby Doo always said: "And I would have gotten away with it, if it hadn't been for those meddling kids!"
travisgriggs 2y ago
This is cool enough. But I find the "celebrification" style of the piece a bit off putting. Did I really need to see multiple posed shots of this young man reposing in various university settings? It's like we need our own version of La La Land to glorify the survivors of computer success to motivate more to participate.
- dabauws 2y ago
  I presume you've never read any quanta magazine pieces before. They like to talk about & emphasize the human side of these discoveries too, instead of merely focusing on the abstract. "It's like we need our own version of La La Land to glorify the survivors of computer success to motivate more to participate." lol what
  - lupire 2y ago
    Specifically, they focus on the human interest part, and a pop science into to the field, and avoid discussing the actual result, because the closer they get to the actual piece of research, the more mistakes they make in describing it.
  - jart 2y ago
    It wouldn't be so cringe if they talked about the technical side too. The article says nothing about what "tiny pointers" are. Andrew Krapivin doesn't have a GitHub with any code. His paper is gated so I can't read it. Do they expect me to venerate this kid on faith? We should be celebrating developers whose work is open source, but instead the establishment relegates them to the lowly thankless role of janitors. The only reason a pop science journo would write an article about an open source developer would be not to lionize them but rather put them in their place for a code of conduct violation.
    - Davidzheng 2y ago
      First link is to arxiv
- OJFord 2y ago
percentcer 2y ago
"arrowlike entities"
- pteraspidomorph 2y ago
  I read that and my mind filled in "...from outer space?"
lupire 2y ago
The older a conjecture is, the more likely it is false. That's why the conjecture resists proof -- there is an counterexample that people aren't seeing.
throwme_123 2y ago
Is someone aware of a GitHub repo with an implementation of this?
- sternma 2y ago
  Put my attempt here: https://github.com/sternma/optopenhash https://github.com/sternma/optopenhash
pmags 2y ago
Nice result! <rhetorical> Hmm....I wonder how such research gets funded?... </rhetorical>
- _dark_matter_ 2y ago
  Private equity or die trying
- starspangled 2y ago
  What do you mean by the rhetorical question?
  - pmags 2y ago
    I'm suggesting that a logical question that readers of Hacker News might want to consider when they get excited about a new result in CS, Physics, Biology, etc. is what are the practical circumstances that fostered these results? i.e. How did someone get paid to work on these problems? In this case the funding source was NSF... This is particularly pertinent to ongoing attacks on the federal research infrastructure of the United States: * The current administration has proposed to cut NSF's funding from $9B/year to $3B/year. * The current administration is trying to impose retroactive changes to already negotiated grant indirects that will result in budget shortfalls of hundreds of millions of dollars. One immediate consequence of this is dramatically fewer graduate students will be admitted to graduate programs across the board; undergraduate summer research programs will be shut down; etc.
ziofill 2y ago
"it is well known that a vital ingredient of success is not knowing that what you are attempting can’t be done." — Terry Pratchett (equal rites)
- yas_hmaheshwari 2y ago
  The fool didn't knew it was impossible. So he did it ( I don't know who said it, but if forced, I will say Albert Einstein or Mark Twain :-) )
  - dpiers 2y ago
    This explains a lot about Ork Mekboyz.
kittikitti 2y ago
I read through this and I'm not sure if people have heard of dictionary trees for hash tables. Of course, quantamagazine.org has been known to sensationalize these types of things.
- nijave 2y ago
  Like TreeMap in Java? Not sure what algorithms are commonly used
monort 2y ago
Talk by the inventor: https://www.youtube.com/watch?v=ArQNyOU1hyE https://www.youtube.com/watch?v=ArQNyOU1hyE
- joaohaas 2y ago
  Thanks for the video, def a lot better than the article. I do find it a bit weird that this is somehow better than just over-allocating (and thus reducing the chances of key collisions, which also makes worst case 'less worse') given his approach also allocates more memory through the aux arrays.
  - hydroreadsstuff 2y ago
    Overallcoation has a limit. You only have so much RAM/storage. Beyond that you start swapping. I could really use a hash table (or similar structure) that degrades less with higher occupancy.
  - rocqua 2y ago
    Could it be that overallocation means you need a bigger search to find empty places or answer queries?
  - sigbottle 2y ago
    He's not allocating through aux arrays, he's splitting the already allocated memory into log(n) layers. You can just track those aux arrays with math in the implementation. It's probably not better than over-allocating except in memory constrained scenarios. But the overhead of funnel hashing is not high - it requires 0 extra memory
  - yencabulator 2y ago
    I don't think anybody is really saying it is. Academics treat big-Oh performance on very very full hash tables like a sport. Real world code on real world CPUs often has a more complex cost function than what the academics considered; cache sizes, fitting in a cacheline, memory bandwidth, icache pressure, ...
- abetusk 2y ago
EternalFury 2y ago
What’s the time and space complexity of the new approach?
ThinkBeat 2y ago
Do we have some nice implementations yet? I do better reading code than math.
merillecuz56 2y ago
[dead]
aqueueaqueue 2y ago
How full is your typical production hashtable?
- ludston 2y ago
  Usually somewhere around seven.
  - aqueueaqueue 2y ago
    Ah so 86%. Gotcha!
foota 2y ago
I guess the most we could hope for here is that this leads to some other discovery down the road, either in hashtables or maybe one of the similar structures like bloom filters?
jheriko 2y ago
i feel this article is missing some detail or incorrect in reporting the actual development here. either that or i am missing something myself... hash tables are constant time on average for all insertion, lookup and deletion operations, and in some special cases, which i've seen used in practice very, very often, they have very small constant run-time just like a fixed-size array (exactly equivalent in-fact). this came up in an interview question i had in 2009 where i got judged poorly for deriding the structure as "not something i've often needed", and i've seen it in much older code. i'm guessing maybe there are constraints at play here, like having to support unbounded growth, and some generic use case that i've not encountered in the wild...?
- yxhuvud 2y ago
  What you are missing is how the hash table behaves when it is almost full. If there is one empty spot left in the whole table, how do you find it when you insert a new entry?
  - sfn42 2y ago
    Same way you find it when doing a lookup later? I know that's probably a naive answer, I honestly don't even know how a hash table works. I know how a hash map works, at least some implementations use a linked list as a bucket. So the hash gives you the bucket, then you linear search the bucket for the element. Buckets should be small so the time to search them is negligible, giving O(1) lookup and insert performance. Obviously this is different from what's being discussed here, this data structure doesn't even really get "full" but it's also the only implementation I know is in practical use. Not sure why one might use a hash table instead
    - yxhuvud 2y ago
      So using buckets with linked lists like that is neither space efficient or fast. A strategy that nowadays is more common and fast is to store conflicts in the table itself using some strategy to find a place in the table itself to put the new entry. The simplest (but not optimal) way to do this is to just take the next one that isn't used yet. This means a linear scan that once the table gets close to being full will approach O(n). To avoid this, better strategies for choosing the next place to look is used, as well as automatic resizing of the hash table at some occupancy percentage to keep the lookup chains short. Other strategies in use will also approach O(n) but will require resizing on difference occupancy percentage. What is new in this approach is that they manage to go faster than O(n) even at almost full occupancy.
_1tan 2y ago
Neat, started on some implementation: https://kraftwerk.social/innovation-in-hash-tables/ https://kraftwerk.social/innovation-in-hash-tables/
seinecle 2y ago
Anyone competent enough here to venture a guess on the speed gain to expect under various scenarios?
abetusk 2y ago
Ok, big shout out to monort [0] for the link to the video [1]. This is just a quick overview from a single viewing of the video, but it's called "funnel hashing". The idea is to split into exponentially smaller sub arrays, so the first chunk is n/m, the second is n/(m^2), etc. until you get down to a single element. Call them A0, A1, etc., so |A0| = n/m, |A1| = n/(m^2) etc., k levels in total. Try inserting into A0 c times. If it fails, try inserting into A1 c times. If it fails, go down the "funnel" until you find a free slot. Call \delta the fraction of slots that are empty (I'm unclear if this is a parameter that gets set at hash table creation or one that's dynamically updated). Setting c = log(1/d) and k = log(1/d) to get worst case complexity O(log^2(1/d)). This circumvents Yao's result by not being greedy. Yao's result holds true for greedy insertion and search policies and the above is non-greedy, as it's cascading down the funnels. There are probably many little hairy details to work out but that's the idea, as far as I've been able to understand it. People should let me know if I'm way off base. This very much reminds me of the "Distinct Elements in Streams" idea by Chakraborty, Vinodchandran and Meel[2]. [0] https://news.ycombinator.com/item?id=43007860 https://news.ycombinator.com/item?id=43007860 [1] https://www.youtube.com/watch?v=ArQNyOU1hyE https://www.youtube.com/watch?v=ArQNyOU1hyE [2] https://arxiv.org/pdf/2301.10191 https://arxiv.org/pdf/2301.10191
- golly_ned 2y ago
  That it circumvents Yao’s conjecture by being non-greedy contradicts the article. Is the article wrong or is your understanding of the paper? I don’t know, just want to see if you’re noticing something the article’s authors don’t know.
  - abetusk 2y ago
    Can you elaborate? From the article: > Farach-Colton, Krapivin and Kuszmaul wanted to see if that same limit also applied to non-greedy hash tables. They showed that it did not by providing a counterexample, a non-greedy hash table with an average query time that’s much, much better than log x.
    - cma 2y ago
froh 2y ago
(2021) for the paper itself https://arxiv.org/abs/2111.12800 https://arxiv.org/abs/2111.12800
- gield 2y ago
  That is the paper Krapivin read in ~2023 and inspired him. The actual paper with the breakthrough is from January 2025: https://arxiv.org/abs/2501.02305 https://arxiv.org/abs/2501.02305.
  - froh 2y ago
    ah! I stand corrected. thanks!
elcritch 2y ago
Anyone else think this could be used with distributed hash tables to dramatically speed up searching or building them? Maybe more exoticly to LLMs and lookup tables. A clever algorithm like this should be applicable in a lot of more specialized data structures or applications. It's likely a DHT would greatly benefit from this sort of algorithmic reduction in time and be less susceptible to constant factor overheads (if there are any).
hoseja 2y ago
Is this just theoretically better O(n) or is there an actually faster implementation somewhere?
sternma 2y ago
For anyone looking for a PoC implementation, here's python: https://github.com/sternma/optopenhash https://github.com/sternma/optopenhash
- rurban 2y ago
  This is overly complicated, both variants. See https://github.com/MWARDUNI/ElasticHashing https://github.com/MWARDUNI/ElasticHashing for a much simplier approach
deleted 2y ago
[deleted]
DeathArrow 2y ago
And we are taught to not try reinventing the wheel!
- drpossum 2y ago
  What wheel was reinvented here?
isaacfrond 2y ago
The paper is here: https://arxiv.org/pdf/2111.12800 https://arxiv.org/pdf/2111.12800 Curiously, Andrew Krapivin, the genious undergrad in the article, is not one of the authors.
- sd9 2y ago
  This is the actual paper: https://arxiv.org/abs/2501.02305 https://arxiv.org/abs/2501.02305
- jtbetz22 2y ago
  Krapivin's work was a result of his study of the Tiny Pointers paper; his paper has already been linked in another response.
- rurban 2y ago
  Did anyone see the code? I didn't find anything on gitlab nor github. Edit: Elastic Hashing found https://github.com/MWARDUNI/ElasticHashing https://github.com/MWARDUNI/ElasticHashing Want to find out if it's only academic or also realistic, and esp. within which bounds.
bruce343434 2y ago
Ok so what's the algorithm? Ass article
nexawave-ai 2y ago
I would like to see this being applied practically. Is there a video demonstrating this or is it still too soon? Is the algorithm secret sauce or will it be open sourced?
victor106 2y ago
> The team’s results may not lead to any immediate applications Why not?
- mortarion 2y ago
  Because it's theoretical math and if you translate it to computer code it might actually be slower.
tomohawk 2y ago
[dead]
reportgunner 2y ago
Sad that the article doesn't say what his approach actually is.
cb321 2y ago
For a different, perhaps more practical take on small pointers in hash tables, you might find this interesting: https://probablydance.com/2018/05/28/a-new-fast-hash-table-in-response-to-googles-new-fast-hash-table/ https://probablydance.com/2018/05/28/a-new-fast-hash-table-i... with contemporaneous discussion at https://news.ycombinator.com/item?id=17176713 https://news.ycombinator.com/item?id=17176713
hemant1041 2y ago
Interesting read!
matsemann 2y ago
The intro picture about pointers in a drawer immediately reminded me of a talk I saw at FUN with Algorithms 2018 called Mind the Gap that gave me an aha moment about leaving space in data structures. Cool then to try to locate it, and see that it was by the same professor in the article, Martín Farach-Colton. Not sure if it's viewable somewhere. But the conference itself was so fun. https://sites.google.com/view/fun2018/home https://sites.google.com/view/fun2018/home I'm not an academic and got my company to sponsor a trip to this Italian island to relax on the beach and watch fun talks, heh.
pizza 2y ago
Just realized that the Mixture of Million Experts paper from last year is similar in some respects to this tiny pointers idea
Canigou 2y ago
I unfortunately did not study well enough to understand the paper. Can someone explain to me how this isn't some kind of Dewey Decimal Classification (https://en.wikipedia.org/wiki/Dewey_Decimal_Classification https://en.wikipedia.org/wiki/Dewey_Decimal_Classification) ?
bnly 2y ago
Step one: Be a genius Step two: Try to solve hard problems Step three: Avoid reading too much of other people's work in the area Step four: (Maybe) Invent a brilliant new solution But really, really don't skip step one.
shaganer 2y ago
Read this within my half hour break and man, wow what a story. I'm not a software guy, I'm a sys and net guy. Despite not caring or knowing about hash tables, that articles a great read! Thanks for sharing!

1304 points by Jhsto 2y ago

varjag 2y ago

tl;dr sublinear worst case query and insertion in hash tables.

bean-weevil 2y ago
Specifically, (log x)^2
pinoy420 2y ago
Eli5?
- laweijfmvo 2y ago
  hash tables are most famous for their O(1) lookup time, but then you have to deal with collisions. There's many famous ways of dealing with collisions and you can convince yourself of their [worst case] lookup time. The article is discussing a new upper bound on that worst case.
  - SilasX 2y ago
    This is always a point of frustration for me. Under the normal big-O model, hashtables aren't, and can't be O(1) lookup, even for the mythic perfect hash function! You can only get the O(1) figure by breaking the big-O model and bolting on some in-practice assumptions[1] that are used nowhere else in discussion of asymptotic complexity. Specifically, as you resize the table, you need a function with a bigger output space to give you more places to store the item. To have a bigger output space, you unavoidably have to do more computations. If you go from a function with n possible outputs to one with 2n possible outputs, as n goes to infinity, you eventually have to use a function with more steps. [1] elaborated on in this earlier discussion: https://news.ycombinator.com/item?id=9807739 https://news.ycombinator.com/item?id=9807739 Specifically this comment about the extra assumptions: https://news.ycombinator.com/item?id=9813524 https://news.ycombinator.com/item?id=9813524
    - Aunche 2y ago
      To be fair, in tree tables, we also assume that comparison is a constant time operation as well when it also necessarily needs to be O(log(n)) for an arbitrary sized table, making it an O(log(n)^2) data structure by this standard.
      - meribold 2y ago
        You don't need to compare the whole key most of the time. I think the amortized cost for a comparison is in O(1).
        sltkr 2y ago
        Not in a balanced tree, since the further down the tree you go, the longer the shared prefix between the search key and node key becomes. So the complexity becomes something like 1 + 2 + 3 + .. + log n = O(log^2 n).
        meribold 2y ago
        Good point. Perhaps we could store the length of the common prefix from the last time we went left as well as from the last time we went right. The minimum of those two should remain a common prefix with the search key for the rest of the lookup and should therefore be safe to skip during subsequent comparisons.
        SilasX 2y ago
        But that would actually help it because you can store how far down the match is by that point in the tree, and know how few digits you have to actually compare.
    - magicalhippo 2y ago
      Your sense of frustration seems to stem from thinking about something which is similar to big-O, but not actually being big-O. All of the points you raise are valid if you want to have a good understanding of actual runtime cost of an algorithm. None of it is relevant if you want to compare algorithms according to big-O, in order to find one which doesn't lead to failure[1] when faced with large amounts of data. Perhaps you should define your own big-R notation for what you're after. [1]: https://arstechnica.com/information-technology/2013/12/exponential-algorithm-making-windows-xp-miserable-could-be-fixed/ https://arstechnica.com/information-technology/2013/12/expon...
  - anothernewdude 2y ago
    O(1) lookup is bullshit that ignores the memory hierarchy.
- tejohnso 2y ago
  If you're trying to find an available cubby hole for your boots, you'll find one very quickly if they're almost all empty. But if they're almost all full, it will take longer for you find one. This discovery shows that it won't take as long as previously thought.

sam0x17 2y ago

This is huge, when can we get a rust implementation?

natpalmer1776 2y ago
Be the change you want to see in the world!
maujim 2y ago
claude one-shot it, then open source it, and build from there
- DC-3 2y ago
  Sounds like a really good way to get a robust implementation of a fiddly and novel algorithm.

duskwuff 2y ago

Paper: https://arxiv.org/pdf/2111.12800 https://arxiv.org/pdf/2111.12800

something98 2y ago
This is the correct (2025) paper. https://arxiv.org/abs/2501.02305 https://arxiv.org/abs/2501.02305

qntty 2y ago

A cool result, but it seems like it should be called a computer science conjecture

ayhanfuat 2y ago
Especially considering “data science” is nowhere near 40 years old.
- Tetraslam 2y ago
  https://www.rcseng.ac.uk/library-and-publications/library/blog/mapping-disease-john-snow-and-cholera/ https://www.rcseng.ac.uk/library-and-publications/library/bl...
- anthk 2y ago
  Statistics are old.
  - speed_spread 2y ago
    On average.
    - lupire 2y ago
      Probably not. Most statistics is new, due to the explosion of interest since the advent of computers.
frabert 2y ago
I think the article's author may have seen the cs.DS classification on the arxiv and assumed it meant Data Science instead of Data Structures
- nerdponx 2y ago
  It's also possible that they don't actually know the difference, or was even asked to change it by an editor to make it sound more trendy. Skepticism of even good journalism is healthy. Gell-Mann amnesia and all.

jjallen 2y ago

Is it just me or did the article not go in to how the improvement works, just the speed of it?

pinoy420 2y ago
It didn’t really go in to either. It doesn’t have any sort of benchmarking or any best/worst case fits?
- Ar-Curunir 2y ago
  This is a theory of CS paper. The algorithm might not even be implementable.
jjallen 2y ago
I was very interested in the improvement. That is the crux of the subject if you ask me.
reportgunner 2y ago
Yeah usually when article starts by explaining what is known or tells you a story they do it to fluff up the text and bait you into reading because the actual content you want is not there.

amazingamazing 2y ago

This is a good test because it’s recent. Let’s see if deep research can come up with this result without just copying this. Edit: gpt4, Gemini 2 and Claude had no luck. Human driven computer science is still safe.

rvz 2y ago
Original thought or additional intuitive improvements such as this discovery is what we should be looking for. This can come from anywhere in the world. The best part is, it did NOT discovered from an AI program.
- azinman2 2y ago
  And yet those who want AGI often talk about the potential for AI to solve all our major problems.
- ANighRaisin 2y ago
  It would be better if it came from AI, as it would show that AI will be able to make helpful improvements to technology. AI has come up with impartments to other algorithms, such as matrix multiplication, so it's not super farfetched for it to come up with something similar to this, especially with all the improvements to AI lately. So much pessimism about AI...
itishappy 2y ago
Do you think the results would be different if you tried this with, say, a cohort of PhD students?
refulgentis 2y ago
I'm so confused trying to imagine exactly what you prompted. What did you prompt?!
- amazingamazing 2y ago
  I told it is was possible, the worst case runtime characteristics and asked it to figure out how you would achieve it. I also gave it some hints from the paper.

orlp 2y ago

Skimming the paper [1], the key difference they used is that their hash table insertion algorithm will probe further than the first empty slot, instead of greedily filling the first empty slot it finds. They combine this with a clever probing sequence which provably finds empty slots efficiently, even if the table is very full. This means insertions when the hash table is less full are slower, but you avoid the worst-case scenario where you're probing for the last (few) remaining open slot(s) without any idea as to where they are. [1]: https://arxiv.org/pdf/2501.02305 https://arxiv.org/pdf/2501.02305 --- An interesting theoretical result but I would expect the current 'trick' of simply allocating a larger table than necessary to be the superior solution in practice. For example, Rust's hashbrown intentionally leaves 1/8th (12.5%) of the table empty, which does cost a bit more memory but makes insertions/lookups very fast with high probability.

SiempreViernes 2y ago
But you could do some hybrid, where you do greedy fill for a while and then switch to this fancier fill once your table is approaching full (using some heuristic)?
- gizmo 2y ago
  Not really because you have to use the same algorithms during subsequent lookups. Imagine you add a bunch of items with insert algorithm A, then you cross some threshold and you insert some more items with Algorithm B. Then you delete (tombstone) a bunch of items. Now you look up an item, and the slot is filled, and you're stuck. You have to proceed your lookup with both algorithms to find what you're looking for (thereby giving up any performance benefits) because the current occupancy doesn't tell you anything about the occupancy at the time when the item you were looking for was inserted.
- layer8 2y ago
  I would assume that you need to start early to be able to reap the benefits once the table is almost full.
- DevelopingElk 2y ago

joe_the_user 2y ago

The theoretical properties of hash table always seemed so impressive to me that they bordered on magic (and this just extends them). What seemed crazy was how they could be so much better than trees, which to me were intuitively the most efficient way to store data. What I realized is that the theory of hash tables involves a fixed-sized collection of objects. For this fixed collection, you create a hash-function and used that like a vector-index and store the collection in a (pre-allocated) vector. This gives a (fuzzy-lens'd) recipe for O(1) time insert, deletion and look-up. (The various tree structures, in contrast, don't assume a particular size). The two problems are you have to decide size beforehand and if your vector gets close to full, you insert etc processes might bog-down. So scanning the article, it seems this is a solution to the bogging down part - it allows quick insertion to a nearly-full table. It seems interesting and clever but actually not a great practical advance. In practice, rather than worrying a clever way to fill the table, I'd assume you just increase your assumed size. Edit: I'm posting partly to test my understanding, so feel to correct me if I'm not getting something.

vessenes 2y ago
It looks to me like the idea is, as you generally describe, that you segment your table into a 2d structure (well conceptually) and proceed to fill one ‘row’ at a time until it’s about 75% full, at which point you move on to the next one. I don’t have time to fully grok the paper, but they claim this makes insertion consistently fast (I believe this until we’re at 75% of total capacity, but maybe they have some other mode for filling when they’re at 75% in every row?). They also claim retrieval is fast, and I didn’t read enough to understand how even retrieval works, or why it is faster. I’ll put out that there a lot of times that it would be really nice to have a nearly full hash table still, you know, work. You can’t always change the size of one during execution of a program. And, in some environments memory counts a lot. That said, I would like to see and play with an implementation — I’m not sure this is ‘worth it’ in the general case. It is also probably cache inefficient, as are most things about hash tables, with the exception of linear probing for reading out of a fairly full one, in which case, you get to just keep pulling stuff directly out of memory to check it. So, it’s not clear to me that this is performance wise worth it. Anyway, I’d like to fully understand it, it seems like an interesting new idea.

MR4D 2y ago

Reading through this article is like reading a description of the Monty-Hall problem. [0] It's as through the conclusion seems to defy common sense, yet is provable. [1] [0] - https://priceonomics.com/the-time-everyone-corrected-the-worlds-smartest/ https://priceonomics.com/the-time-everyone-corrected-the-wor... [1] - 2nd to the last paragraph: "The fact that you can achieve a constant average query time, regardless of the hash table’s fullness, was wholly unexpected — even to the authors themselves."

darknavi 2y ago
I always really enjoyed the Numb3rs lecture on Monty-Hall https://www.youtube.com/watch?v=P9WFKmLK0dc https://www.youtube.com/watch?v=P9WFKmLK0dc
ryao 2y ago
> “Our brains are just not wired to do probability problems very well, so I’m not surprised there were mistakes,” Stanford stats professor Persi Diaconis told a reporter, years ago. “[But] the strict argument would be that the question cannot be answered without knowing the motivation of the host.” This is wrong. Let’s label the goats A and B to simplify things (so we do not need to consider the positions of the doors). There are 3 cases: 1. You pick the right door. The other two doors have goats. The host may only choose a goat. Whether it is A or B does not matter. 2. You pick the door with goat A. The host may only choose goat B. 3. You pick the door with goat B. The host may only choose goat A. The host’s intentions are irrelevant as far as the probability is concerned (unless the host is allowed to tell the contestant which door is correct, but I am not aware of that ever being the case). 2/3 of the time, you pick the wrong door. In each of those cases, the remaining door is correct. The most strict argument is yet another statistics professor got basic statistics wrong.
- CrazyStat 2y ago
  I can assure you Diaconis didn’t get it wrong. > "The problem is not well-formed," Mr. Gardner said, "unless it makes clear that the host must always open an empty door and offer the switch. Otherwise, if the host is malevolent, he may open another door only when it's to his advantage to let the player switch, and the probability of being right by switching could be as low as zero." Mr. Gardner said the ambiguity could be eliminated if the host promised ahead of time to open another door and then offer a switch. The hosts’s intentions absolutely do matter, because the problem (as originally stated) doesn’t specify that the host always opens a door and offers a switch. Maybe he only offers a trade when you initially picked the good door.

ascorbic 2y ago

And they wouldn't make him first named author on the paper

yacin 2y ago
it's common in math/cs theory papers to have the order of authors be alphabetical rather than in descending order of contribution.
- writebetterc 2y ago
  Good, but that can also be noted in a subtitle right below the authors (I've seen this in papers myself!)
  - Ar-Curunir 2y ago
    The paper is not targeted at laymen, but other members of the research community, who are aware of the author ordering convention.
- mometsi 2y ago
  I wonder if there's a significant nominative determinism effect-- One might expect some of the most prominent people in math and cs theory to have names like Aaronson and Baez...
  - chikere232 2y ago
    It would be most fair to hash the names first, especially for this paper
    - usefulcat 2y ago
      I suppose then the next question will be which author gets to choose the hash function..
      - 2y ago

default-kramer 2y ago

> And for this new hash table, the time required for worst-case queries and insertions is proportional to (log x)2 — far faster than x. > The team’s results may not lead to any immediate applications I don't understand why it wouldn't lead to immediate applications. Is this a situation where analysis of real-world use cases allows you to tune your hash implementation better than what a purely mathematical approach would get you?

jeffbee 2y ago
Complexity analysis and actual systems programming have been diverging for a while. I don't see anything in the paper that will inform practice.
- naasking 2y ago
  How so?
  - zamadatix 2y ago
    Even when something isn't a galactic algorithm "how well it maps to being done efficiently in real hardware with hardware sized data sizes" is more and more often the important bit over "slightly better bounds at infinity". The former is probing the edge of mathematics while the latter is probing the edges of practical construction so they rarely seem to align much anymore at these depths.
    - gauge_field 2y ago
      A contributing factor is how complex/smart the current hardware is. It can have cache line size, different forms of hardware/software prefetching, different ports for different ops, memory latency, simd extensions. These leave many opportunities for algorithms to be optimized over. There is also the issue of real life scenarios not matching with asymptotic ones (due to e.g., size of input), which when coupled with previous factors, leads to even more potential optimization schemes. Obligatory reference: https://agner.org/optimize/ https://agner.org/optimize/

brink 2y ago

Krapivin made this breakthrough by being unaware of Yao's conjecture. The developer of Balatro made an award winning deck builder game by not being aware of existing deck builders. I'm beginning to think that the best way to approach a problem is by either not being aware of or disregarding most of the similar efforts that came before. This makes me kind of sad, because the current world is so interconnected, that we rarely see such novelty with their tendency to "fall in the rut of thought" of those that came before. The internet is great, but it also homogenizes the world of thought, and that kind of sucks.

aidenn0 2y ago
> I'm beginning to think that the best way to approach a problem is by either not being aware of or disregarding most of the similar efforts that came before. This makes me kind of sad, because the current world is so interconnected, that we rarely see such novelty with their tendency to "fall in the rut of thought" of those that came before. The internet is great, but it also homogenizes the world of thought, and that kind of sucks. I think this is true only if there is a novel solution that is in a drastically different direction than similar efforts that came before. Most of the time when you ignore previous successful efforts, you end up resowing non-fertile ground.
- layman51 2y ago
  Right, the other side is when you end up with rediscoveries of the same ideas. The example that comes to my mind is when a medical researcher found the trapezoidal rule for integration again[1]. [1]: https://fliptomato.wordpress.com/2007/03/19/medical-researcher-discovers-integration-gets-75-citations/ https://fliptomato.wordpress.com/2007/03/19/medical-research...
  - sitkack 2y ago
    I think that shows how great the trapezoidal rule is. I feel like this is brought out too many times, that now it is used to make fun of people. It is 18 years old at this point.

ryao 2y ago

j-scott 2y ago
I think this was meant as a reply to https://news.ycombinator.com/item?id=43004919 https://news.ycombinator.com/item?id=43004919
- deleted 2y ago
  [deleted]

dooglius 2y ago

It looks like the result only matters in the case where the hash table is close to full. But couldn't one just deal with this case by making the table size 10% bigger? (Or, if it is resizeable, resizing earlier)

nhumrich 2y ago
Yes, which is what most real world hash tables do. They resize themselves once hash collision is too probable.
xxs 2y ago
In reality 75% is the standard fill factor for linear probe that also exhibits the best locality (if the table gets too full it just allocated double (or x) the memory, and copies the existing entries). Most non-linear probe tables (e.g. cookoo) suffer due to the fact RAM is not 'random' at all.

quantum2022 2y ago

This is neat! I always wondered if there would be a way to 'containerize' tables like this. IE a regular table is like a bulk carrier ship, with everything stuffed into it. If you could better organize it like a container ship, you could carry much more stuff more efficiently (and offload it faster too!)

doublerabbit 2y ago
Easy stuff. Convert table row to a string, json to whatever Apply base16 to the that variable You've now got a base16 string of that data. Create a hash table, setup a key value for that base16 string. You now have a container holding the data. All you need to do is decode the hex string and you've got base32 data.
- internetter 2y ago
  What you just described is magnitudes slower than even conventional hash tables
  - doublerabbit 2y ago
    I'd like to see your solution.
    - internetter 2y ago
      My solution would be a conventional hash table. Now, I will consider using the solution defined in the paper.
      - doublerabbit 2y ago
        Yeah? Not for me. I prefer my way of things. More fun and learning.
- deleted 2y ago
  [deleted]

trebligdivad 2y ago

Anyone got a simple implementation of 'Tiny pointers'? My mind prefers code/pseudo-code first rather than the proof.

zombiwoof 2y ago

Take that AI :)

jimnotgym 2y ago

Now we have faster data structures we can fill that extra time by writing less efficient code, and loading more pointless libraries. This is the march of computer science.

nickhodge 2y ago

I bet this guy would still fail a first round FAANG developer interview requiring a Hash Table solution to move on in the process. "Yeah, sorry. You didn't use the right Hash Table"

rswail 2y ago
Which is exactly the difference between "programming" and "computer science".
- justanotherjoe 2y ago
  Oh, come on. Anyone can use a hash table. What this man did is not even comparable to that.

ChrisMarshallNY 2y ago

As the villain in Scooby Doo always said: "And I would have gotten away with it, if it hadn't been for those meddling kids!"

travisgriggs 2y ago

This is cool enough. But I find the "celebrification" style of the piece a bit off putting. Did I really need to see multiple posed shots of this young man reposing in various university settings? It's like we need our own version of La La Land to glorify the survivors of computer success to motivate more to participate.

dabauws 2y ago
I presume you've never read any quanta magazine pieces before. They like to talk about & emphasize the human side of these discoveries too, instead of merely focusing on the abstract. "It's like we need our own version of La La Land to glorify the survivors of computer success to motivate more to participate." lol what
- lupire 2y ago
  Specifically, they focus on the human interest part, and a pop science into to the field, and avoid discussing the actual result, because the closer they get to the actual piece of research, the more mistakes they make in describing it.
- jart 2y ago
  It wouldn't be so cringe if they talked about the technical side too. The article says nothing about what "tiny pointers" are. Andrew Krapivin doesn't have a GitHub with any code. His paper is gated so I can't read it. Do they expect me to venerate this kid on faith? We should be celebrating developers whose work is open source, but instead the establishment relegates them to the lowly thankless role of janitors. The only reason a pop science journo would write an article about an open source developer would be not to lionize them but rather put them in their place for a code of conduct violation.
  - Davidzheng 2y ago
    First link is to arxiv
OJFord 2y ago

percentcer 2y ago

"arrowlike entities"

pteraspidomorph 2y ago
I read that and my mind filled in "...from outer space?"

lupire 2y ago

The older a conjecture is, the more likely it is false. That's why the conjecture resists proof -- there is an counterexample that people aren't seeing.

throwme_123 2y ago

Is someone aware of a GitHub repo with an implementation of this?

sternma 2y ago
Put my attempt here: https://github.com/sternma/optopenhash https://github.com/sternma/optopenhash

pmags 2y ago

Nice result! <rhetorical> Hmm....I wonder how such research gets funded?... </rhetorical>

_dark_matter_ 2y ago
Private equity or die trying
starspangled 2y ago
What do you mean by the rhetorical question?
- pmags 2y ago
  I'm suggesting that a logical question that readers of Hacker News might want to consider when they get excited about a new result in CS, Physics, Biology, etc. is what are the practical circumstances that fostered these results? i.e. How did someone get paid to work on these problems? In this case the funding source was NSF... This is particularly pertinent to ongoing attacks on the federal research infrastructure of the United States: * The current administration has proposed to cut NSF's funding from $9B/year to $3B/year. * The current administration is trying to impose retroactive changes to already negotiated grant indirects that will result in budget shortfalls of hundreds of millions of dollars. One immediate consequence of this is dramatically fewer graduate students will be admitted to graduate programs across the board; undergraduate summer research programs will be shut down; etc.

ziofill 2y ago

"it is well known that a vital ingredient of success is not knowing that what you are attempting can’t be done." — Terry Pratchett (equal rites)

yas_hmaheshwari 2y ago
The fool didn't knew it was impossible. So he did it ( I don't know who said it, but if forced, I will say Albert Einstein or Mark Twain :-) )
- dpiers 2y ago
  This explains a lot about Ork Mekboyz.

kittikitti 2y ago

I read through this and I'm not sure if people have heard of dictionary trees for hash tables. Of course, quantamagazine.org has been known to sensationalize these types of things.

nijave 2y ago
Like TreeMap in Java? Not sure what algorithms are commonly used

monort 2y ago

Talk by the inventor: https://www.youtube.com/watch?v=ArQNyOU1hyE https://www.youtube.com/watch?v=ArQNyOU1hyE

joaohaas 2y ago
Thanks for the video, def a lot better than the article. I do find it a bit weird that this is somehow better than just over-allocating (and thus reducing the chances of key collisions, which also makes worst case 'less worse') given his approach also allocates more memory through the aux arrays.
- hydroreadsstuff 2y ago
  Overallcoation has a limit. You only have so much RAM/storage. Beyond that you start swapping. I could really use a hash table (or similar structure) that degrades less with higher occupancy.
- rocqua 2y ago
  Could it be that overallocation means you need a bigger search to find empty places or answer queries?
- sigbottle 2y ago
  He's not allocating through aux arrays, he's splitting the already allocated memory into log(n) layers. You can just track those aux arrays with math in the implementation. It's probably not better than over-allocating except in memory constrained scenarios. But the overhead of funnel hashing is not high - it requires 0 extra memory
- yencabulator 2y ago
  I don't think anybody is really saying it is. Academics treat big-Oh performance on very very full hash tables like a sport. Real world code on real world CPUs often has a more complex cost function than what the academics considered; cache sizes, fitting in a cacheline, memory bandwidth, icache pressure, ...
abetusk 2y ago

EternalFury 2y ago

What’s the time and space complexity of the new approach?

ThinkBeat 2y ago

Do we have some nice implementations yet? I do better reading code than math.

merillecuz56 2y ago

[dead]

aqueueaqueue 2y ago

How full is your typical production hashtable?

ludston 2y ago
Usually somewhere around seven.
- aqueueaqueue 2y ago
  Ah so 86%. Gotcha!

foota 2y ago

I guess the most we could hope for here is that this leads to some other discovery down the road, either in hashtables or maybe one of the similar structures like bloom filters?

jheriko 2y ago

i feel this article is missing some detail or incorrect in reporting the actual development here. either that or i am missing something myself... hash tables are constant time on average for all insertion, lookup and deletion operations, and in some special cases, which i've seen used in practice very, very often, they have very small constant run-time just like a fixed-size array (exactly equivalent in-fact). this came up in an interview question i had in 2009 where i got judged poorly for deriding the structure as "not something i've often needed", and i've seen it in much older code. i'm guessing maybe there are constraints at play here, like having to support unbounded growth, and some generic use case that i've not encountered in the wild...?

yxhuvud 2y ago
What you are missing is how the hash table behaves when it is almost full. If there is one empty spot left in the whole table, how do you find it when you insert a new entry?
- sfn42 2y ago
  Same way you find it when doing a lookup later? I know that's probably a naive answer, I honestly don't even know how a hash table works. I know how a hash map works, at least some implementations use a linked list as a bucket. So the hash gives you the bucket, then you linear search the bucket for the element. Buckets should be small so the time to search them is negligible, giving O(1) lookup and insert performance. Obviously this is different from what's being discussed here, this data structure doesn't even really get "full" but it's also the only implementation I know is in practical use. Not sure why one might use a hash table instead
  - yxhuvud 2y ago
    So using buckets with linked lists like that is neither space efficient or fast. A strategy that nowadays is more common and fast is to store conflicts in the table itself using some strategy to find a place in the table itself to put the new entry. The simplest (but not optimal) way to do this is to just take the next one that isn't used yet. This means a linear scan that once the table gets close to being full will approach O(n). To avoid this, better strategies for choosing the next place to look is used, as well as automatic resizing of the hash table at some occupancy percentage to keep the lookup chains short. Other strategies in use will also approach O(n) but will require resizing on difference occupancy percentage. What is new in this approach is that they manage to go faster than O(n) even at almost full occupancy.

_1tan 2y ago

Neat, started on some implementation: https://kraftwerk.social/innovation-in-hash-tables/ https://kraftwerk.social/innovation-in-hash-tables/

seinecle 2y ago

Anyone competent enough here to venture a guess on the speed gain to expect under various scenarios?

abetusk 2y ago

Ok, big shout out to monort [0] for the link to the video [1]. This is just a quick overview from a single viewing of the video, but it's called "funnel hashing". The idea is to split into exponentially smaller sub arrays, so the first chunk is n/m, the second is n/(m^2), etc. until you get down to a single element. Call them A0, A1, etc., so |A0| = n/m, |A1| = n/(m^2) etc., k levels in total. Try inserting into A0 c times. If it fails, try inserting into A1 c times. If it fails, go down the "funnel" until you find a free slot. Call \delta the fraction of slots that are empty (I'm unclear if this is a parameter that gets set at hash table creation or one that's dynamically updated). Setting c = log(1/d) and k = log(1/d) to get worst case complexity O(log^2(1/d)). This circumvents Yao's result by not being greedy. Yao's result holds true for greedy insertion and search policies and the above is non-greedy, as it's cascading down the funnels. There are probably many little hairy details to work out but that's the idea, as far as I've been able to understand it. People should let me know if I'm way off base. This very much reminds me of the "Distinct Elements in Streams" idea by Chakraborty, Vinodchandran and Meel[2]. [0] https://news.ycombinator.com/item?id=43007860 https://news.ycombinator.com/item?id=43007860 [1] https://www.youtube.com/watch?v=ArQNyOU1hyE https://www.youtube.com/watch?v=ArQNyOU1hyE [2] https://arxiv.org/pdf/2301.10191 https://arxiv.org/pdf/2301.10191

golly_ned 2y ago
That it circumvents Yao’s conjecture by being non-greedy contradicts the article. Is the article wrong or is your understanding of the paper? I don’t know, just want to see if you’re noticing something the article’s authors don’t know.
- abetusk 2y ago
  Can you elaborate? From the article: > Farach-Colton, Krapivin and Kuszmaul wanted to see if that same limit also applied to non-greedy hash tables. They showed that it did not by providing a counterexample, a non-greedy hash table with an average query time that’s much, much better than log x.
  - cma 2y ago

froh 2y ago

(2021) for the paper itself https://arxiv.org/abs/2111.12800 https://arxiv.org/abs/2111.12800

gield 2y ago
That is the paper Krapivin read in ~2023 and inspired him. The actual paper with the breakthrough is from January 2025: https://arxiv.org/abs/2501.02305 https://arxiv.org/abs/2501.02305.
- froh 2y ago
  ah! I stand corrected. thanks!

elcritch 2y ago

Anyone else think this could be used with distributed hash tables to dramatically speed up searching or building them? Maybe more exoticly to LLMs and lookup tables. A clever algorithm like this should be applicable in a lot of more specialized data structures or applications. It's likely a DHT would greatly benefit from this sort of algorithmic reduction in time and be less susceptible to constant factor overheads (if there are any).

hoseja 2y ago

Is this just theoretically better O(n) or is there an actually faster implementation somewhere?

sternma 2y ago

For anyone looking for a PoC implementation, here's python: https://github.com/sternma/optopenhash https://github.com/sternma/optopenhash

rurban 2y ago
This is overly complicated, both variants. See https://github.com/MWARDUNI/ElasticHashing https://github.com/MWARDUNI/ElasticHashing for a much simplier approach

deleted 2y ago

[deleted]

DeathArrow 2y ago

And we are taught to not try reinventing the wheel!

drpossum 2y ago
What wheel was reinvented here?

isaacfrond 2y ago

The paper is here: https://arxiv.org/pdf/2111.12800 https://arxiv.org/pdf/2111.12800 Curiously, Andrew Krapivin, the genious undergrad in the article, is not one of the authors.

sd9 2y ago
This is the actual paper: https://arxiv.org/abs/2501.02305 https://arxiv.org/abs/2501.02305
jtbetz22 2y ago
Krapivin's work was a result of his study of the Tiny Pointers paper; his paper has already been linked in another response.
rurban 2y ago
Did anyone see the code? I didn't find anything on gitlab nor github. Edit: Elastic Hashing found https://github.com/MWARDUNI/ElasticHashing https://github.com/MWARDUNI/ElasticHashing Want to find out if it's only academic or also realistic, and esp. within which bounds.

bruce343434 2y ago

Ok so what's the algorithm? Ass article

nexawave-ai 2y ago

I would like to see this being applied practically. Is there a video demonstrating this or is it still too soon? Is the algorithm secret sauce or will it be open sourced?

victor106 2y ago

> The team’s results may not lead to any immediate applications Why not?

mortarion 2y ago
Because it's theoretical math and if you translate it to computer code it might actually be slower.

tomohawk 2y ago

[dead]

reportgunner 2y ago

Sad that the article doesn't say what his approach actually is.

cb321 2y ago

For a different, perhaps more practical take on small pointers in hash tables, you might find this interesting: https://probablydance.com/2018/05/28/a-new-fast-hash-table-in-response-to-googles-new-fast-hash-table/ https://probablydance.com/2018/05/28/a-new-fast-hash-table-i... with contemporaneous discussion at https://news.ycombinator.com/item?id=17176713 https://news.ycombinator.com/item?id=17176713

hemant1041 2y ago

Interesting read!

matsemann 2y ago

The intro picture about pointers in a drawer immediately reminded me of a talk I saw at FUN with Algorithms 2018 called Mind the Gap that gave me an aha moment about leaving space in data structures. Cool then to try to locate it, and see that it was by the same professor in the article, Martín Farach-Colton. Not sure if it's viewable somewhere. But the conference itself was so fun. https://sites.google.com/view/fun2018/home https://sites.google.com/view/fun2018/home I'm not an academic and got my company to sponsor a trip to this Italian island to relax on the beach and watch fun talks, heh.

pizza 2y ago

Just realized that the Mixture of Million Experts paper from last year is similar in some respects to this tiny pointers idea

Canigou 2y ago

I unfortunately did not study well enough to understand the paper. Can someone explain to me how this isn't some kind of Dewey Decimal Classification (https://en.wikipedia.org/wiki/Dewey_Decimal_Classification https://en.wikipedia.org/wiki/Dewey_Decimal_Classification) ?

bnly 2y ago

Step one: Be a genius Step two: Try to solve hard problems Step three: Avoid reading too much of other people's work in the area Step four: (Maybe) Invent a brilliant new solution But really, really don't skip step one.

shaganer 2y ago

Read this within my half hour break and man, wow what a story. I'm not a software guy, I'm a sys and net guy. Despite not caring or knowing about hash tables, that articles a great read! Thanks for sharing!