CityHash
Encyclopedia
CityHash is a family of non-cryptographic
hash functions, designed for fast hashing of strings
. It has 64-, 128-, and 256-bit variants.
Google developed the algorithm in-house starting in 2010. The C++
source code for the reference implementation of the algorithm was released in 2011 under an MIT license
, with credit to Geoff Pike and Jyrki Alakuijala. The authors expect the algorithm to outperform previous work by a factor of 1.3 to 2.5, "largely due to higher instruction-level parallelism." CityHash is influenced by and partly based on MurmurHash
.
Some particularly fast CityHash functions depend on CRC32 instructions that are present in SSE4.2. Others are designed to be portable, though they will run best on little-endian 64-bit CPUs.
The reference code comments warn that it has not been tested on big-endian platforms.
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
hash functions, designed for fast hashing of strings
String (computer science)
In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....
. It has 64-, 128-, and 256-bit variants.
Google developed the algorithm in-house starting in 2010. The C++
C++
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
source code for the reference implementation of the algorithm was released in 2011 under an MIT license
MIT License
The MIT License is a free software license originating at the Massachusetts Institute of Technology . It is a permissive license, meaning that it permits reuse within proprietary software provided all copies of the licensed software include a copy of the MIT License terms...
, with credit to Geoff Pike and Jyrki Alakuijala. The authors expect the algorithm to outperform previous work by a factor of 1.3 to 2.5, "largely due to higher instruction-level parallelism." CityHash is influenced by and partly based on MurmurHash
MurmurHash
MurmurHash is a non-cryptographic hash function suitable for general hash-based lookup. It was created by Austin Appleby in 2008, and exists in a number of variants, all of which have been released into the public domain.-Variants:...
.
Some particularly fast CityHash functions depend on CRC32 instructions that are present in SSE4.2. Others are designed to be portable, though they will run best on little-endian 64-bit CPUs.
The reference code comments warn that it has not been tested on big-endian platforms.
External links
- Official site
- Introducing CityHash, Announcement by Google