Google City Hash Family
Google has released a free license of the new family of hash functions CityHash for strings. So far, the functions CityHash64 and CityHash128 for receiving 64- and 128-bit hash codes are presented.
According to the developers , in real conditions CityHash64 exceeds the speed of similar hash functions by at least 30%.
Because of their simplicity, these hash functions are not suitable for cryptographic applications, but theoretically this is an ideal option for hash tables. True, the code is still damp, not tested enough (see warning ) and needs some refinement.
CityHash128 is optimized for lines of at least a few hundred bytes and with a sufficient length of lines exceeds CityHash64 in speed. On small lines it is slower. Inside Google, it is used in cases where you need to minimize the number of collisions.
')
Although they tried to optimize the functions for processors that are located in Google data centers, it turned out that they work very quickly on most PCs and laptops. It supports 64-bit registers, instruction-level parallelism and fast access to unaligned data in memory.
Traditionally, the main advantage of Google’s development is performance. And here, too, they put this first priority. CityHash hash function is made on the basis of well-known developments, and MurmurHash , created by Austin Appleby in 2008, became the main model. This is a simple and fast general purpose hash function that is not cryptographically secure. All its variants are in free use.
The main advantage of the Google approach is that most steps contain at least two independent mathematical operations. As it turned out, modern CPUs better cope with this kind of code.
The reverse side of the coin - the code becomes more complicated than in other popular hash functions. But the developers decided to optimize it for performance, not for simplicity, and even added special options for executing the function for short lines of input data.
It is strange that the developers did not show specific benchmarks, if they declare speed as the main advantage of their hash function. Here is the performance of some popular hash functions from the Austin Appleby website (he also developed the SMHasher program to test the speed of hash functions):
According to the developers , in real conditions CityHash64 exceeds the speed of similar hash functions by at least 30%.
Because of their simplicity, these hash functions are not suitable for cryptographic applications, but theoretically this is an ideal option for hash tables. True, the code is still damp, not tested enough (see warning ) and needs some refinement.
CityHash128 is optimized for lines of at least a few hundred bytes and with a sufficient length of lines exceeds CityHash64 in speed. On small lines it is slower. Inside Google, it is used in cases where you need to minimize the number of collisions.
')
Although they tried to optimize the functions for processors that are located in Google data centers, it turned out that they work very quickly on most PCs and laptops. It supports 64-bit registers, instruction-level parallelism and fast access to unaligned data in memory.
Traditionally, the main advantage of Google’s development is performance. And here, too, they put this first priority. CityHash hash function is made on the basis of well-known developments, and MurmurHash , created by Austin Appleby in 2008, became the main model. This is a simple and fast general purpose hash function that is not cryptographically secure. All its variants are in free use.
The main advantage of the Google approach is that most steps contain at least two independent mathematical operations. As it turned out, modern CPUs better cope with this kind of code.
The reverse side of the coin - the code becomes more complicated than in other popular hash functions. But the developers decided to optimize it for performance, not for simplicity, and even added special options for executing the function for short lines of input data.
It is strange that the developers did not show specific benchmarks, if they declare speed as the main advantage of their hash function. Here is the performance of some popular hash functions from the Austin Appleby website (he also developed the SMHasher program to test the speed of hash functions):
OneAtATime - 354.163715 mb / sec FNV - 443.668038 mb / sec SuperFastHash - 985.335173 mb / sec lookup3 - 988.080652 mb / sec MurmurHash 1.0 - 1363.293480 mb / sec MurmurHash 2.0 - 2056.885653 mb / sec
Source: https://habr.com/ru/post/117360/
All Articles