current position:Home>[Java data structure & algorithm] I'd rather kill myself than others. 9 hash table principle

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

2022-01-26 23:13:18 I'm Xiaobai

【Java data structure & Algorithm 】️ I'd rather be tired to death , Also kill others 9️ Hash table principle


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

 Insert picture description here


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 :

 Insert picture description here
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 . Insert picture description here

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

 Insert picture description here
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

copyright notice
author[I'm Xiaobai],Please bring the original link to reprint, thank you.

Random recommended