6 ms·
Hash Functions
- adamzochowski 3y agoThere is a fourth category of hash functions: find similar items. For English words, this is usually done with soundex / metaphone / doublemetaphone. Fun fact, soundex was developed over 100 years ago to help immigrants find their families in USA even if they didn't know how to spell their last name. Soundex is supported by most DBs. For images, there are hashes like ahash/phash/dhash/whash/blockmeat/colormoment/colorhas/marrHildreth . Most popular Audio hash is acoustid. There was also EchoPrint (with two incompatible versions), but once EchoNest was bought out by Spotify the public support and development into echoprint died. Some groups of people tried to keep echoprint alive but I am unaware if it is still used by anyone publicly.
- esafak 3y agoToday you would use embeddings optimized for similarity search.
- nighthawk454 3y agoEmbedding models are still essentially a hash function, just very complex ones
- esafak 3y agoMoreover, and crucially, they are learned.
- scentoni 3y agoThose are examples of useful functions. They are not examples of useful hash functions.
- gabetax 3y agoSpecifically, these functions to not provide "uniform distribution".
- jagged-chisel 3y agoThat isn’t a requirement of an algorithm called a hash function
- gabetax 3y agoFrom the article: > For a function to be useful as a hash function, it must exhibit the property of uniform distribution It's also listed as the first property on the Wikipedia page: https://en.wikipedia.org/wiki/Hash_function#Uniformity https://en.wikipedia.org/wiki/Hash_function#Uniformity
- jagged-chisel 3y agoI can’t find the text you quoted. The article starts off: > A hash function is any function that can be used to map data of arbitrary size to fixed-size values And the first sentence in the section you link says > A good hash function should map the expected inputs as evenly as possible over its output range. It doesn’t have to be “good” to be a hash function.
- anamexis 3y agoThat's not a meaningful definition of a hash function, then. def hash(val): return 0
- jagged-chisel 3y agoYes, this is a hash function. Whether it’s “useful” or “good” is the purview of the architect. Tangential edit: https://xkcd.com/221/ https://xkcd.com/221/
- lynndotpy 3y agoIf I remember correctly, Apple's Voxel Net (~2018 neural network, used for doing machine learning on sparse lidar point-cloud data) uses a simple "spatial hash" for this purpose, using the coordinate of the voxel as a key.
- dimatura 3y agoYeah, hashing for spatial data is a fairly common technique (and not invented for that paper). It totally makes sense for applications where there is a need to index sparse data in a potentially very large or even unbounded physical space. There's some hashes that are specialized for keys that are 3-dimensional points or voxel coordinates, but almost any off-the-shelf hash will do if applied to say, the concatenated indices of a voxel in a given coordinate frame.
- joezydeco 3y agoSoundex is still out there. If you live in Illinois, Florida, or Wisconsin your drivers license number is a soundex hash of your name combined with your birthday. http://www.highprogrammer.com/alan/numbers/dl_us_shared.html http://www.highprogrammer.com/alan/numbers/dl_us_shared.html
- xorvoid 3y agoTIL! Fascinating! Of course my first thought was.. “what about hash collisions?” And naturally each state has selected their own resolution. In Illinois you can apparently be detained for a while due to a hash collision with a suspect.. plate numbers aren’t unique apparently!?
- joezydeco 3y agoLicense plate numbers are unique. Two somewhat similar names can resolve to the same Drivers License number, but in those (extremely rare) cases it's just a matter of checking the actual name against the warrant.
- jll29 3y agoRobert C. Russell (and Margaret King Odell) invented SOUNDEX, which is described in US Patent 1,261,167 (1918) -see also Knuth (1973) TAOCP vol. 3. https://patentimages.storage.googleapis.com/31/35/a1/f697a3ab85ced6/US1261167.pdf https://patentimages.storage.googleapis.com/31/35/a1/f697a3a...
- michaelcampbell 3y agoWhile researching Soundex in the mid/late 80's, I of course soundex'd my last name and realized that it was the first part of my state's driver's license #.
- metadat 3y agoIntriguing, I just checked mine and it seems California doesn't appear to do this. If you're comfortable sharing, would like to find out which state you're referring to. Cheers.
- ComputerGuru 3y agoAnother poster shared this link: http://www.highprogrammer.com/alan/numbers/dl_us_shared.html http://www.highprogrammer.com/alan/numbers/dl_us_shared.html It has the encoding formula for Wisconsin, Illinois, and Florida (which match the parent's comment) but there may be others.
- michaelcampbell 3y agoMine was Illinois. I got it in the early 1980's, and moved away shortly thereafter, so no idea if they still do. Weirdly, I remember that # even now. Soundex-???-2DigitYearOfBirth-??? Looks like at least the format has changed since then.
- deleted 3y ago[deleted]
- preseinger 3y agohash functions are ultimately just a mapping of an input set of high/infinite cardinality to an output set of fixed/finite cardinality you correctly point out that some hash functions exist which map input words in some specific language into similarity groups based on some concept of semantics but this is essentially unrelated to the topics raised in the linked article
- Genbox 3y agoThey are called similarity digests or sometimes "fuzzyhashing". For generic files there are Context Triggered Piecewise Hashing (CTPH), Trend Micro Locality Sensitive Hash (TLSH) and Similary Digest Hash (SDHash)
- deleted 3y ago[deleted]
- layer8 3y agoI don’t understand the encryption use case. Can someone elaborate?
- tptacek 3y agoIt's not written super clearly (though the article itself is an interesting and ambitious piece of technical writing) but the impression I get is that he's referring to the role of hash functions in cryptosystems: for signatures, transcript hashes, key derivation, channel binding, and things like that. Cryptographic hash functions are the glue that binds crypto protocols together. But you can also trivially turn a hash function into a cipher and encrypt with it (apologies if I missed an explanation of this in the article). Just hash a key and a counter together to create a keystream and XOR your plaintext to it. That's how Salsa20 and ChaCha20 work. (Interestingly, the reverse process --- converting a block cipher into a hash function --- is where we historically get our cryptographic hash functions from).
- layer8 3y agoI’m familiar with hash functions for signatures, however I’m confused about the mention for encryption, in particular with respect to the context of common schemes like AES and RSA. I guess hashing a key is an option though.
- commandersaki 3y agoModern hashing functions pretty much offer encryption out of box like gimli or BLAKE2 family (I think they call it XOF mode). This is pretty much thanks to the sponge construction.
- tptacek 3y agoYou can spitball a hash-based stream cipher with any hash function in just a couple lines of python. Take a 128 bit key string, and then hash it with an incrementing counter to get successive 32 bytes of keystream data, just like you would with AES in CTR mode.
- fnordpiglet 3y agoMy favorite use is for distribution / sharding of work in distributed systems, or for distributed locality of work in such a system.