[HN Gopher] Implementing Hash Tables in C
___________________________________________________________________
Implementing Hash Tables in C
Author : todsacerdoti
Score : 157 points
Date : 2021-10-16 17:17 UTC (5 hours ago)
(HTM) web link (www.andreinc.net)
(TXT) w3m dump (www.andreinc.net)
| olav wrote:
| Nice article. Since the beginning of the 1990s I enjoy using the
| hash tables implemented by John Ousterhout for Tcl:
| https://core.tcl-lang.org/tcl/file?name=generic/tclHash.c&ci...
| SavantIdiot wrote:
| Similarly, Robert Sedgewick covered this in his 1990's book
| "Algorithms in C" quite nicely, and a bit more succinctly, IMO.
|
| https://www.amazon.com/Algorithms-Computer-Science-Robert-Se...
| chrisseaton wrote:
| When I was an undergraduate my university used a test of 'can you
| implement a hash table in C' as their basic 'can you really
| program' test to stream incoming students.
| Swizec wrote:
| Back then that was likely true. Just like building linked lists
| from scratch was on the same level as writing a basic loop
| nowadays
|
| High level programming languages have come a long way in the
| past 20 years. So many things we no longer need to think about
| in normal day to day programming
| chrisseaton wrote:
| You can also build a hash table from scratch in for example
| Ruby. The language doesn't matter and C isn't the key bit of
| the problem.
| marginalia_nu wrote:
| Dunno, I've had use from knowing how to implement hash tables
| several times just in the last few months. Extremely useful
| stuff if you are working with memory mapped data that is
| larger than system memory.
| Swizec wrote:
| Of course it's useful. My argument is that it's no longer
| necessary for most programmers. Almost every language now
| comes with a native good enough hash table implementation.
| yakubin wrote:
| It's necessary when you need to debug something,
| regardless of who wrote the implementation, now it's
| you're responsibility.
| pjmlp wrote:
| If they want to be allowed to write Engineer so-and-so,
| yes it is necessary.
| xmprt wrote:
| I'm not sure what you're saying? That someone's not a
| real engineer unless they can implement a hash table?
| Firstly, I don't think any programmers are classified as
| engineers by law in some countries. Secondly, I don't
| think I've even once thought about implementing any high
| school/college data structures at work because all of
| them have libraries with much better implementations.
| pjmlp wrote:
| Any software engineering degree in countries with
| professional titles has algorithm and data structures as
| compulsory lecture, and exam.
| dboat wrote:
| What countries are these you keep referring to?
| tharkun__ wrote:
| I don't know what he was referring to specifically but I
| this would be the first time that I hear of a country
| that actually has a protected title of _Software_
| Engineer.
|
| Plenty protect "Engineer" meaning "Software Engineer" is
| actually a title that you _can not_ hold.
|
| As for the "mandatory courses on algorithms" and such if
| you go to university, definitely Germany. If you go to
| university and study computer science, the first few
| courses which you will have to pass before ever getting
| to choose your own courses are going to be about
| modelling, data structures and algorithms. You will learn
| the theory of hashing, you will learn how to model
| problems you will learn various sorting algorithms etc.
| in the lecture. Labs will make you implement various of
| these things on an actual computer. An exam will probably
| ask you to write one or two of these algorithms in pseudo
| code. Been there, done that. And of course comparing all
| manner of algorithms in Big-O notation etc. Also
| "reducing" one algorithm onto another (dunno if that's
| the proper term in English). But basically taking an
| algorithm that you know the run time of and showing that
| a different algorithm you have has the same
| characteristics and thus Big-O complexity. You will also
| learn about P/NP and will implement bin packing and such.
|
| Unrelated to hash tables but hashing always reminds me of
| substring search algorithms that we learned about. The
| naive way is to just do a "text" search, advancing one
| character at a time and comparing the whole thing to your
| substring. I don't remember what the algorithm is called
| or who invented it but we learned about an optimization
| for substring search, which hashes with a particular hash
| function and when advancing a character in the string to
| search through, you reverse the part of the function for
| the first character and only add the result of the
| function for the next character. Thus you save having to
| deal with the characters that haven't changed at all.
|
| Just like hash tables or linked lists, I've never needed
| to code any of these ever again and I just use them, but
| it was definitely worth learning about all this stuff.
| dudeman13 wrote:
| That's laughable. Software "engineers" pretending that
| "software engineer" is a protected title in any way or
| form (including soft and metaphorical community based
| protection).
|
| We'll get to call software engineers actual engineers
| when they can lose their (currently not existent) license
| over malpractice, not a second before that happens.
|
| The tech industry cheapens the term "engineer". The
| discipline isn't nearly enough mature to be called that
| pjmlp wrote:
| It certainly is in many countries, where one isn't
| legally allowed to call themselves as such after a 6
| weeks bootcamp.
| lazide wrote:
| Do you have any cites for that?
|
| I'm not aware of any that even attempt to hold software
| engineers to any sort of Professional Engineer standard,
| or have a mechanism that one could actually comply if
| they did.
|
| I do know of some areas where a PE is required for some
| software engineers, like some nuke or aerospace shops,
| but they're very very few in number - and the PE isn't
| about the software part of it.
| formerly_proven wrote:
| In Germany you can only call yourself an engineer if you
| actually have a technical degree (details and exact
| implications vary by state). "Software Engineer" might or
| might not fall under that regulation, though it is
| probably the reason why most job ads in German will call
| for "Software developers" not "engineers".
| lazide wrote:
| Sure enough, thanks! Looked it up and it seems like
| Engineer is the protected title, which plausibly would
| apply (Ingenieur formally).
| Swizec wrote:
| Just like you had to learn how to code with absolute
| memory addressing because only a silly non-engineer would
| waste computer resources on a compiler, right?
| pjmlp wrote:
| Yes, programming in Assembly is usually also a possible
| assignment during a 5 year degree.
| formerly_proven wrote:
| That's why it's called a computer science degree, not a
| gluing-libraries-together degree.
| louthy wrote:
| > High level programming languages have come a long way in
| the past 20 years
|
| Have they? How? It seems to me that we're not very far away
| from where we were. Yeah we're running on better tin, but the
| programming languages are pretty much the same - at least the
| mainstream ones are.
|
| > So many things we no longer need to think about in normal
| day to day programming
|
| I'm always surprised when I read comments like this. It's not
| necessarily wrong, but all programmers writing anything less
| than trivial will bump into limitations of the various types
| of data-structures eventually. Not understanding the trade-
| offs and not being able to make informed decisions about
| different approaches will be a problem. We may not have to
| write them ourselves, but we should certainly understand how
| they're implemented in my opinion.
|
| I may be a special case in that I started programming on
| machines with tiny amounts of memory and with slow CPUs, and
| have spent time writing core data structures when in the
| games industry in the 90s, and now in my _large web-
| application life_ have a large open-source library [1] which
| is all core data structures; but I honestly couldn 't imagine
| being a successful developer without a key understanding of
| these things.
|
| [1] https://github.com/louthy/language-ext
| Swizec wrote:
| > Not understanding the trade-offs and not being able to
| make informed decisions about different approaches will be
| a problem. We may not have to write them ourselves, but we
| should certainly understand how they're implemented in my
| opinion.
|
| I agree. My argument is that they are no longer something
| everyone needs to know how to implement to be considered
| "can code at all".
| marginalia_nu wrote:
| I think perhaps the explanation why modern applications
| seem as slow as, or in many cases slower than their Windows
| 3.11 equivalents loading stuff off a floppy disk, may be
| this general disregard for choosing good data structures.
|
| We have a hardware that's thousands, if not a million times
| faster, yet it hardly seems to matter when the code is a
| thousand, if not a million times slower.
| klyrs wrote:
| I do a lot of low-level stuff by choice. Early in my
| career, I fell into web development because I got a job
| offer from a friend, and I found myself writing for loops
| and various SQL queries. On a good day, I got to write a
| regex. Hell, these days, you hardly need for loops in
| javascript because they're hidden by frameworks. It was
| boring as all get-out, so I got out of the industry, went
| to university and learned a whole lot about programming. I
| try not to be elitist about it; I think it's important to
| acknowledge that a _ton_ of people in the industry have a
| radically different perspective on the nature of
| programming.
| matheusmoreira wrote:
| Not needing to think about stuff anymore implies the ability
| to do so when needed. Somehow I doubt people who have always
| relied on language features and libraries would be able to
| work effectively without them should they ever need to.
| whimsicalism wrote:
| I think I'd have trouble with the hashing function but unless
| you're using a basic modulo.
| cle wrote:
| IMO this is the least interesting part of a question like
| "can you write a hash table", unless you're in an area where
| writing hash functions is a critical skill. You have to deal
| with collisions either way...the ideal solution for me
| testing someone's _software engineering_ skills would be one
| that uses a crappy hash function, but can trivially swap it
| out for something better. (Maybe this is different than what
| a school is testing for though?)
| vidarh wrote:
| I agree. If I gave a test like that and someone gave me an
| answer where the hash function was pretty much just a dummy
| I'd be fine with that as long as they were clearly aware it
| was just a dummy and hopefully could explain roughly the
| characteristics of a good hash function.
| DudeInBasement wrote:
| search_index = value & ((hash_length_power_of2) - 1)
| armeehn wrote:
| Unless I'm missing something, the definition of H_division is
| misleading. The co-domain (image) set is really {0, ..., M - 1},
| which _is_ surely a subset of [0, M), although definitely very
| different in size. Usually it's written as Z/qZ where q = M.
|
| Neat article otherwise. It reminded me of mappings to real
| numbers which I always found interesting during my undergrad.
| ufo wrote:
| > The % operation is quite efficient (although it's usually two
| times more expensive than multiplication);
|
| I though it was much more than two times slower? Division and
| modulus are the slowest integer operation.
| veltas wrote:
| It makes a significant difference in profiling, versus i.e. a
| bitwise mask to find a modulus for a power-of-two size.
| pansa2 wrote:
| Agner Fog's manual lists a latency/reciprocal-throughput of
| 15/10 for 64-bit divide on Ivy Lake & Tiger Lake, vs 3/1 for
| 64-bit multiply. So division is 5-10x slower than
| multiplication.
|
| https://www.agner.org/optimize/#manuals
| rurban wrote:
| Spare this light article on bad hash tables. The best one in C is
| currently github.com/LIMachi/swiss-table but this is missing the
| security discussion.
| quotemstr wrote:
| Great article --- very little having to do with C though.
|
| It might be unpopular to say this but: can we please stop
| teaching people to write new programs in C? The language is
| inherently unsafe, and we're collectively losing billions of
| dollars per year to preventable memory safety errors.
|
| Why not use Rust or C# or something to demonstrate the principles
| of hash tables? Why start with the programming equivalent of a
| 1950s death crap automobile with a spike in the center of the
| steering wheel?
| glouwbug wrote:
| Driving without power steering has made my arms much stronger,
| and a giant spike capable of ramming through my lungs at
| collision has made me a much safer driver. I can also repair a
| 1950s mobile, because it's mechanical workings are much simpler
| than something modern
| genewitch wrote:
| When I need to borrow your car, I get stabbed in the lungs,
| though.
| pjc50 wrote:
| Genuinely unable to tell if this is continuing the joke or an
| entirely serious but misguided comment.
| kahlonel wrote:
| No, we can't. Because C is a necessary evil. If you stop
| teaching people to program in C, who is going to maintain
| virtually every software this world is running on?
| smackeyacky wrote:
| Out in embedded land, where you will have C, assembler and a
| tiny library if you are lucky, the luxuries of Rust just aren't
| widely available yet. Its also a very valuable language to
| learn since the big 3 operating systems are made out of it. You
| can't wish that away.
| glowmeg wrote:
| Out of curiosity, what kind of embedded device has only C and
| asm support? Usually, the compiler used for these is gcc
| which, for a really long time is written in C++. It shouldn't
| be hard to use even go on embedded now. Also Rust gets
| rustc_codegen_gcc[1], so you will be able to use it
| everywhere.
|
| [1] https://github.com/rust-
| lang/rust/tree/master/compiler/rustc...
| ternaryoperator wrote:
| He seems to overlook a fundamental optimization for open hash
| tables: ordering the elements in the linked list associated with
| each bucket. Right now to find an element, he reads the entire
| linked list if it's not there. By ordering the elements in the
| list upon insertion, he can greatly improve on that.
| Delk wrote:
| Wouldn't ordering basically improve lookup performance at the
| expense of insertion performance? If you don't order the
| elements, you can just smash the new entry at the end of the
| list and be done with it.
|
| Of course that might still be a reasonable trade-off to make.
| Is there experimental (or experiential) support for getting
| significant improvements from ordering?
| ternaryoperator wrote:
| Many (most?) hash tables are write-once, read-many (caches,
| databases, etc. among others) so optimizing for reading makes
| a lot of sense.
| hawk_ wrote:
| ordered insertion can happen in the "middle" of the list.
| unordered always has to reach the end (to ensure no
| duplicate) so it's worse for insertion as well.
| Delk wrote:
| Good point. For some reason I didn't think about duplicate
| checking even though it's pretty obvious.
| louthy wrote:
| For maximum performance they should be implemented as tries. I
| believe the Compressed Hash-Array Mapped Prefix-tree (CHAMP)
| [1] is considered the current _state of the art_ in terms of
| performance, memory efficiency, and memory locality.
|
| I have an implementation here [2] that is used for the HashMap
| and HashSet types in language-ext. The 'guts' of the
| implementation is here [3]
|
| [1] https://michael.steindorfer.name/publications/phd-thesis-
| eff...
|
| [2] https://github.com/louthy/language-
| ext/blob/main/LanguageExt...
|
| [3] https://github.com/louthy/language-
| ext/blob/main/LanguageExt...
| loeg wrote:
| Hashmaps that have string-like keys suitable for indexing a
| trie are a subset of all hashmaps.
| sltkr wrote:
| This is possible, but typically this is not done for generic
| hash tables because it requires keys to be ordered (i.e. there
| must be a function that can tell whether one key is less than,
| greater than, or equal to another) while the current
| implementation only requires testing for equality.
| nyc_pizzadev wrote:
| Every hash table implementation I have done I use an RB tree
| for each bucket. This way if the bucket is loaded with hundreds
| or thousands of elements, you aren't penalized too badly.
| ufo wrote:
| I wish this article were more opinionated.
|
| One of my pet peeves about hash tables is that most of the
| resources about it describe how there are dozens of different
| ways to do it (different hash functions, different collision
| management, etc), but they often don't tell you which one you
| should choose.
| FullyFunctional wrote:
| I had hoped for a little more insight and information density,
| but I did learn about Knuth's hash x(x+3) % P which was news to
| me.
|
| However these are all techniques that I might have used in
| undergrad, but today I would hands down use Cuckoo hashing unless
| the application domain was insertion dominated.
| veltas wrote:
| Open addressing or 'open bucket' hash tables always seem to be a
| second consideration in textbooks or blogs. I find them generally
| faster, and more memory efficient, and easier to implement.
| Instead we're always taught the closed bucket approach, often
| using linked list buckets of all things.
|
| In certain scenarios open addressing has worse performance, but
| with the right optimisations it's generally only contrived
| situations where it performs worse. In normal usage, open
| addressing has vastly superior locality, a smaller memory
| footprint, and less dereferencing overhead.
|
| A lot of writing and textbooks describing open addressing seem to
| imply that the order of walking through the table when collisions
| occur is really important (and it is). But the approach with best
| performance in practice is to just do a dumb increment through
| the table in-order because of caching... the penalty for that
| simple approach can be made up for with a good, pseudo-random
| hash.
| haberman wrote:
| Lua uses "chained scatter" (linked list, but links point to
| other entries in the same table, to maintain locality):
| https://github.com/lua/lua/blob/master/ltable.c
|
| This is a good visual depiction of chained scatter:
| https://book.huihoo.com/data-structures-and-algorithms-with-...
|
| Inspired by Lua, I did the same for upb
| (https://github.com/protocolbuffers/upb). I recently
| benchmarked upb's table vs SwissTable for a string-keyed table
| and found upb was faster in both insert and lookup (in insert
| upb is beating SwissTable by 2x).
|
| It's true that the links do create more memory overhead though.
| cassepipe wrote:
| So here is what I just learnt from
| https://programming.guide/hash-tables-open-addressing.html:
|
| Open adressing = When there is a collision, that is when the
| memory slot is already taken, you just put your key in the next
| one (linear probing), or at squared increment (quadratic
| probing) or at an increment determined by another hash
| function. Howewer all those techniques seems to be suffering
| from clustering and the more elaborate ones trying to trade
| memory locality for less clustering. I guess it just depends on
| how long and what scale you are going to need a hash table ?
| veltas wrote:
| The clustering can still happen with any walk. The dumb walk
| is the best, but it is the most prone to clustering if the
| hash is simplistic. But if the hash is pseudo-random, it's as
| likely to get clusters as any other walk, and has better
| locality.
| pcwalton wrote:
| > But the approach with best performance in practice is to just
| do a dumb increment through the table in-order because of
| caching... the penalty for that simple approach can be made up
| for with a good, pseudo-random hash.
|
| SwissTable, which is generally among the fastest hash tables
| around, doesn't do this. It does chunks of 16 entries each,
| then starts skipping chunks (so first 0 chunks are skipped,
| then 1, then 2, etc.) The chunk skipping behavior helps avoid
| O(n) behavior on pathological cases.
| veltas wrote:
| The O(n) behavior is not even really that 'pathological',
| lots of normal cases get that behavior. If SwissTable
| operates as you say, then it sounds like it is prone to bad
| performance for lots of normal data with a dumb hash, i.e. as
| a "Set" on numbers where the hash is the identity function (a
| valid hash for a closed bucket hash table), and many of the
| numbers are next to each other.
|
| Therefore, much like the situation I described in my parent
| post, SwissTable would benefit from being used with a decent
| pseudo-random hash. Which is no trouble, there are a number
| of good, fast ones.
| scandox wrote:
| > Cryptographic hash functions are a special family of hash
| functions. For security considerations, they exhibit an extra set
| of properties. The functions used in hash table implementations
| are significantly less pretentious.
| kevin_thibedeau wrote:
| > In modern times, modern compilers can perform all kinds of
| optimizations, including this one. So it's up to you to decide if
| making things harder to read is worth it.
|
| It is still worthwhile to manually perform these arithmetic
| optimizations because you may want to build with optimizations
| off and switching to actual multiplication in hot code paths can
| cause performance regressions.
|
| An unrelated area where I wouldn't do this sort of thing is bit
| twiddling tricks to implement branchless code. That generally
| defeats modern compilers' abilities to generate branchless code
| with conditional moves and ends up being slower.
| chrisseaton wrote:
| > switching to actual multiplication in hot code paths can
| cause performance regressions
|
| Why would you turn off optimisations if you were worried about
| performance optimisations?
| tom_ wrote:
| Simplify use of a debugger. Would be nice if the performance
| is at least bearable when you're doing this.
| matheusmoreira wrote:
| Sometimes the compilers will do insane stuff that causes bugs
| if you enable too much optimization. Usually because of
| strict aliasing violations causing undefined behavior.
| kroltan wrote:
| ...don't violate strict aliasing then?
| matheusmoreira wrote:
| Aliasing is ubiquitous in systems programming.
| Reinterpreting arbitrary types as arrays of bytes, for
| example. Honestly, it's kind of amazing that C even has
| this rule. Seems to be an attempt to be competitive with
| Fortran.
| eperdew wrote:
| This is why the aliasing rules in C explicitly allow
| aliasing any pointer type with a char*.
| matheusmoreira wrote:
| Yeah, but char sucks. It's not a synonym for octet. Not
| guaranteed to be 8 bits. Its signedness is even ambiguous
| unless unsigned is specified.
|
| The correct type is uint8_t/u8. Sadly, using that to
| alias other types is undefined. I've also seen hashing
| algorithms which used uint16_t/u16, with similar aliasing
| optimization bugs. Sometimes you want to reinterpret
| things as a struct, too.
|
| This is the reason why Linux compiles with strict
| aliasing disabled.
| quietbritishjim wrote:
| Aliasing with unsigned char* is also allowed. (Oddly,
| signed char is not, even if char is signed.)
|
| uint8_t is not guaranteed to be unsigned char but in
| practice almost always is. GCC did originally have
| separate 8 bit types when stdint.h was introduced but
| quickly changed to a typedef for char-based types
| precisely to allow using it for aliasing.
|
| Yes, technically char may not be 8 bits but in practice
| that is very rare (and you can statically assert it).
|
| Overall IMO the best solution is always use uint8_t and
| turn off optimisations on those rare weird platforms
| where it's not an alias for unsigned char for whatever
| reason.
| simias wrote:
| I don't understand, if you're trying to work around
| aliasing restrictions why would you use `uint8_t*` in the
| first place?
|
| By definition `sizeof(char) == 1`, so that's almost
| always what you want when messing with types in C anyway.
| What you want is bytes, not octets.
| kevin_thibedeau wrote:
| chars can be two octets on some DSP platforms that lack
| byte addressability.
| loeg wrote:
| sizeof(char) must always be 1, regardless of how many
| bits or octets that represents. On such a platform,
| uint8_t does not exist.
| matheusmoreira wrote:
| > uint8_t is not guaranteed to be unsigned char but in
| practice almost always is.
|
| Does this imply any unsigned char typedef is able to
| alias anything? Or is uint8_t a compiler special case?
| simias wrote:
| `char` is not guaranteed to be 8 bits and in some more
| exotic environments (DSPs for instance) may not be.
|
| IIRC POSIX guarantees that char is 8 bits though (but I
| still think that the sign is implementation-dependent).
|
| But as I said in a parent comment, I don't understand why
| it's even relevant. If you want to alias any type then
| use `char *` and not anything else. I don't understand
| why one would prefer using stdint for that.
| matheusmoreira wrote:
| Because sometimes people need to reinterpret data as an
| array of 8/16/32/64 bit elements. Sometimes people also
| need to reinterpret things as a structure.
|
| This is independent of how many bytes the underlying
| platform can address. If we have 8 bit processing code
| but the platform can only address 16 bits at a time, it
| should be up to the compiler to generate code that works.
| Compilers already do stuff like that in other
| circumstances.
| jeffbee wrote:
| Those people need to be copying, otherwise the
| reinterpretation might not be working. The char data
| might not be correctly aligned, for example. Recently
| went through a big nightmare where a C++ codebase that
| had accreted on x86 was thought to be ported to another
| platform where alignment actually matters and there were
| all manner of rare low-level malfunctions stemming from
| the idea that you can just wantonly cast a char* to
| structured data.
| jcranmer wrote:
| The strict aliasing rules look through typedefs (and
| const/volatile-qualifiers). It's possible to use char,
| signed char, and unsigned char, or any typedef thereof,
| or any typedef of any typedef, etc., to access any memory
| whatsoever.
| simias wrote:
| It's definitely rife with footguns but you can very much
| write aliasing-safe systems code (or even kernel code,
| for that matter). Or at the very least you should strive
| to contain the alias-infringing code in well delimited
| sections of the source code that are built with special
| flags for instance.
|
| If optimizations break code due to aliasing violations I
| would really recommend fixing the code, not turning the
| optimizations off!
|
| Also if anything C's aliasing is less strict than Fortran
| by default, hence the later introduction of "restrict" to
| allow further optimizations.
| matheusmoreira wrote:
| > you can very much write aliasing-safe systems code (or
| even kernel code, for that matter)
|
| Yeah, sometimes it's possible. Usually by making a mess
| of everything with unions. If I remember correctly, type
| punning with unions is still illegal C code but in
| practice every compiler understands the idiom.
|
| The simple and intuitive solution to many problems is to
| cast the data to the new pointer and work directly with
| it. This should always produce correct code no matter
| what. People think like this and they write code with
| these assumptions in mind. In practice, nobody really
| cares too much what the C standard says. What matters is
| whether the compilers produce the desired code.
| garaetjjte wrote:
| Use -fno-strict-aliasing if you do have such code.
| matheusmoreira wrote:
| I do. The -fno-strict-aliasing and -fwrapv are standard
| flags for me. They essentially fix C the language by
| making it behave reasonably.
| rurban wrote:
| But -fwrapv is broken for decades and will not be fixed.
| matheusmoreira wrote:
| How is it broken?
| rdpintqogeogsaa wrote:
| Note that if you have untrusted input, you may want to use a
| defensive option for hashing involving a private key, such as
| SipHash[1]. Otherwise, an attacker who knows your hash functions
| can just pre-generate a large number of colliding elements and
| reduce your hash function to a linked list; given enough
| attacker-controlled elements, this can effectively amount to a
| DoS attack[2].
|
| [1] https://github.com/veorq/SipHash
|
| [2] https://www.aumasson.jp/siphash/siphashdos_29c3_slides.pdf
| veltas wrote:
| Another alternative is not using a hash table, and instead
| using a sorted binary tree or similar, which tends to be slower
| on average but has worst case O(log n) lookup, O(log n)
| insertion. Depends on your criteria.
| dhosek wrote:
| That depends on the implementation. If it's a simple binary
| tree, the worst case is O(n), not O(log n) since if you
| insert data in sorted order everything will always be in the
| left branch. O(log n) is average lookup time.
|
| If you have a specialized tree structure like a red-black
| tree which will automatically balance, this will improve, but
| sorted input is still a viable attack method.
|
| That said, a lot depends on the application and one should
| pick a hash function wisely. A binary tree-mapped hash table
| works best when you want to be able to iterate on keys in
| sort order or find an entry that's just before or just after
| a non-existent key in sort order. It's not really a good
| defense against hash attacks. On the flip side, the default
| hasher in Rust is hardened against hash attacks, but it's
| overkill for most applications and can cause severe
| performance degradation (although at least the library
| documentation is clear on this and points at alternative hash
| implementations for such cases). Unfortunately, the Rust
| resizing algorithm is flawed and won't resize until the hash
| capacity is completely full1 making hash collisions much more
| likely. I had a doubling of performance in benchmarking some
| code that I was writing just by increasing the initial
| capacity of the map.
|
| [?][?][?]
|
| 1. A common mistake I see Java developers make is, when they
| know they'll be inserting _n_ items into a HashSet or HashMap
| is to initialize the structure with a capacity of _n_. This
| guarantees that Java will end up re-allocating the index
| since the default load factor in Java is 0.55 meaning that
| once you have 0.55x _capacity_ elements in your collection it
| will resize.
| veltas wrote:
| I said 'sorted' but I meant balanced as well. And even if
| you can 'attack' still, there is a limit to how slow it can
| get. Worst case O(log n) is not bad. As for security, I
| can't speak to its efficacy, but I know it's appropriate
| for real-time applications.
| pansa2 wrote:
| SipHash is considerably slower than an unkeyed hash function,
| isn't it? One idea I had to avoid its overhead is to use double
| hashing, with a fast primary hash and SipHash as the secondary
| hash.
|
| Naively this feels as though it should provide good performance
| in the common case and also good security - even if there are
| many primary hash collisions, they won't also be secondary hash
| collisions. Does anyone know if there is an analysis of this
| approach anywhere?
| kgeist wrote:
| Can't you simply salt the output of your simple hash function
| with a randomly-pregenerated salt value? (can be unique for
| each hashtable, a simple integer to be xored) That way the
| attacker can't predict the collision and you have same
| performance as before.
| wongarsu wrote:
| If you salt the output, wouldn't anything that collided
| before salting also collide after salting? Surely you would
| salt the input of the hash function? The effectiveness of
| that kind of depends on your hash function. SipHash tries to
| give you guarantees that your salt is effective and stays
| secret even if hashes (along with unhashed values) ever get
| exposed to the attacker
| haberman wrote:
| A key result of the SipHash paper is that the SipHash authors
| broke common hash functions so completely that they can
| generate _seed-independent_ multicollisions.
|
| That means that certain inputs will collide regardless of
| what the seed is. Seeding the hash function is no defense
| against such an attack.
| wyager wrote:
| If you scramble the _output_ of the hash function, it has to
| be in a way that does not commute with the mapping from hash
| to bucket index. Xor won't cut it for power of two sized hash
| tables.
|
| Should probably just use a keyed hash function like siphash -
| the security analysis is straightforward and these hash
| functions are quite well developed.
| [deleted]
| gautamcgoel wrote:
| The I believe that author gets the value of phi wrong: it is
| roughly 1.618, not 0.618.
| Ambroisie wrote:
| It's its brothe (more accurately its inverse), usually written
| Phi with a bar on top. They both respect the golden ratio.
| Bootvis wrote:
| He probably confused it with 1/phi and didn't check his
| equation.
| kangalioo wrote:
| TIL 1/phi=phi-1
| messe wrote:
| That's essentially the definition. ph is the solution to
| ph^2 - ph - 1 = 0
|
| Which can be re-arranged, by dividing by ph to,
| ph - 1 - 1/ph = 0
|
| or: 1/ph = ph - 1
| marginalia_nu wrote:
| Or
|
| ph^-1=ph-1
| messe wrote:
| Yes, ph^-1 is another way to write 1/ph.
| klyrs wrote:
| Happy phi day ^_^
| lmkg wrote:
| Several ways of defining the Golden Ratio allow either, or
| both. One convention is that upper-case Phi or Ph is
| 1.618[...], while lower-case phi or ph is 0.618[...].
|
| The values are related by ph = 1/Ph, as well as Ph = ph + 1.
| Both of these relations can be derived from the fact that they
| are the ratios of a Golden Rectangle--if a square has length
| one, then adding a rectangle with height ph to the side will
| give a rectangle of length Ph, and the rectangles are Similar.
___________________________________________________________________
(page generated 2021-10-16 23:00 UTC)