Wikipedia:Reference desk/Archives/Computing/2024 August 28
| Computing desk | ||
|---|---|---|
| < August 27 | << Jul | August | Sep >> | Current desk > |
| Welcome to the Wikipedia Computing Reference Desk Archives |
|---|
| The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages. |
August 28
editTreeified and linked-list hash bucket equivalence
editA maximally-unbalanced binary search tree is the same as a sorted singly-linked list except that it has an extra null pointer per node. In hash table implementations such as OpenJDK's HashMap, where hash buckets are linked list by default but hash flooding# attacks are resisted by "treeifying" overcrowded buckets whose keys are at least partially ordered, could this equivalence be exploited to decrease the number of branch instructions further than has so far been achieved? NeonMerlin 23:35, 28 August 2024 (UTC)