# [Java data structure & algorithm] I'd rather kill myself than others. 9 hash table principle

2022-01-26 23:13:18

# summary

Starting today , Xiaobai, I will take you to open Java data structure & A new chapter in algorithms . # Hashtable

Hashtable (Hash Table), According to the key code value (Key Value) Data structure for direct access . Hash table by putting key (key) Map to a location in the table to access records , To speed up the search . Pictured : This mapping function is called the hash function , The records stored are called hash tables . Hash table embodies the idea of space for time in the field of algorithm design .

# hash function

hash function (Hash Function) Also known as hash algorithm , hash function . The hash function converts an input value of any length into a value of fixed length and outputs . Principles for designing hash functions :

1. Uniformity : If a==b, that hash(a) == hash(b)
2. Efficiency : The calculation of hash function should be simple and efficient
3. Homogeneity : As far as possible, let the Hashi value be evenly distributed How hash functions process data :

1. Small integers
• Positive integer : Use it directly
• Negtive integer : Offset to a positive integer and then use
2. Large integer
• Take part : After taking the large integer n position
• Yes m modulus : Usually take the modulus of prime numbers
3. floating-point
• java Use in float and double To represent floating point numbers
• Follow the hash function design to convert floating-point type to integer type
4. character string
• Convert string type to integer processing , Think of string types as 26 A decimal number means
• After calculating the hash value corresponding to the string , For a prime number M Take the module to get the hash function
5. Reference type
• The reference type can be directly applied to the hash function of the string , Get hash value