图解：什么是哈希？

[lovefxs@localhost ~]$ echo -n  "I love J"  | openssl md5 
(stdin)= ef821d9b424fd5f0aac7faf029152e04

[lovefxs@localhost ~]$ echo -n  "I love J"  | openssl md5 
(stdin)= ef821d9b424fd5f0aac7faf029152e04
[lovefxs@localhost ~]$ echo -n  "I love Y"  | openssl md5 
(stdin)= fb49af24bebae07658650ae8eb1c0f5b

using namespace std; 
  
class Hash 
{ 
    int N;    // 哈希表的表长  
    // 指向对应存储下标的指针。
    list<int> *table; 
public: 
    Hash(int V); 
    void insertKey(int x); 
    void deleteKey(int key);     
    int hashFunction(int x) { 
        return (x % N); 
    } 
  
    void displayHash(); 
}; 
  
Hash::Hash(int b) 
{ 
    this->N = b; 
    table = new list<int>[N]; 
} 
  
void Hash::insertKey(int key) 
{ 
    int index = hashFunction(key); 
    table[index].push_back(key);  
} 
  
void Hash::deleteKey(int key) 
{ 
 //计算key的哈希值 Hash(key)
 int index = hashFunction(key); 
  
    //找到 index
    list <int> :: iterator i; 
    for (i = table[index].begin(); 
      i != table[index].end(); i++) { 
     if (*i == key){
   break; 
        }
  } 
  //如果找到了对应的key，删除之
  if (i != table[index].end()) 
    table[index].erase(i); 
} 
  
// 输出哈希表
void Hash::displayHash() { 
    for (int i = 0; i < N; i++) { 
        cout << i; 
     for (auto x : table[i]){
         cout << " --> " << x;             
        } 
     cout << endl; 
    } 
} 
 
int main() 
{ 
    int a[] = {50, 700, 76, 85, 92, 73, 101}; 
    int n = sizeof(a)/sizeof(a[0]); 
  
    Hash h(7);
    for (int i = 0; i < n; i++){
        h.insertKey(a[i]);  
    }  
    h.deleteKey(92); 
    h.displayHash(); 
  
    return 0; 
} 

using namespace std; 
  
// 哈希表的大小 
#define TABLE_SIZE 13 
  
// 用于定义 Hash2(key)
#define PRIME 7 

class DoubleHash { 
    // 定义一个哈希表 
    int* hashTable; //int[] hashTable;
    int curr_size; 
  
public: 
    // 判断哈希表是否满了
    bool isFull() 
    { 
        //当前的大小大于哈希表的大小
        return (curr_size == TABLE_SIZE); 
    } 
  
    // 哈希函数1
    int hash1(int key) 
    { 
        return (key % TABLE_SIZE); 
    } 
  
    // 哈希函数2
    int hash2(int key) 
    { 
        return (PRIME - (key % PRIME)); 
    } 
   
    DoubleHash() 
    { 
        hashTable = new int[TABLE_SIZE]; 
        curr_size = 0; 
        for (int i = 0; i < TABLE_SIZE; i++){
            hashTable[i] = -1;   
        }
    } 
  
    // 插入操作
    void insertHash(int key) 
    { 
        // 判断哈希表是否已满
        if (isFull()) 
            return; 
  
        // 获取哈希函数1计算的结果
        int index = hash1(key); 
  
        // 如果发生碰撞 
        if (hashTable[index] != -1) { 
            //由哈希函数2获取另一个哈希值
            int index2 = hash2(key); 
            int i = 1; 
            while (1) { 
                //得到双重哈希的索引，对于线性探测，平方探测改这里就可以
                int newIndex = (index + i * index2) % TABLE_SIZE; 
  
                //如果新的哈希值newIndex为空，退出循环。
                if (hashTable[newIndex] == -1) { 
                    hashTable[newIndex] = key; 
                    break; 
                } 
                i++; 
            } 
        } 
        else{
            hashTable[index] = key; 
        }
        curr_size++; 
    } 
  
    // 哈希表查找操作
    void search(int key) 
    { 
        int index1 = hash1(key); 
        int index2 = hash2(key); 
        int i = 0; 
        while (hashTable[(index1 + i * index2) % TABLE_SIZE] != key) { 
            if (hashTable[(index1 + i * index2) % TABLE_SIZE] == -1) { 
                cout << key << ":\t哈希表中不存在" << endl; 
                //java 这里自己改成响应输出
                return; 
            } 
            i++; 
        } 
        cout << key << "找到啦！" << endl; 
    } 
  
    // 打印输出
    void displayHash() 
    { 
        for (int i = 0; i < TABLE_SIZE; i++) { 
            if (hashTable[i] != -1) 
                cout << i << " --> "
                     << hashTable[i] << endl; 
            else
                cout << i << endl; 
        } 
    } 
}; 

int main() 
{ 
    int a[] = {50, 700, 76, 85, 92, 73, 101}; 
    int n = sizeof(a) / sizeof(a[0]); 
  
    //创建哈希表，插入a[]中的元素
    DoubleHash h; 
    for (int i = 0; i < n; i++) { 
        h.insertHash(a[i]); 
    } 
    //查找
    h.search(36); //不存在
    h.search(101); //存在
    //打印输出
    h.displayHash(); 
    return 0; 
} 

int newIndex = (index + i) % TABLE_SIZE; 

int newIndex = (index + i*i) % TABLE_SIZE; 

import java.util.ArrayList; 
  
class Map<K, V> { 
  
    class MapNode<K, V> { 
  
        K key; 
        V value; 
        MapNode<K, V> next; //链地址法
  
        public MapNode(K key, V value) 
        { 
            this.key = key; 
            this.value = value; 
            next = null; 
        } 
    } 
  
    // 键值对就存储在
    ArrayList<MapNode<K, V> > hashTable; 
  
    // 装填因子 alpha 的分子 -- 表中填入的记录数
    int size; 
  
    // 装填因子 alpha 的分母 -- 哈希表的长度。
    int numHashTable; 
  
    // 默认的装填因子 0.75 
    final double DEFAULT_LOAD_FACTOR = 0.75; 
  
    public Map() 
    { 
        numHashTable = 5; 
  
        hashTable = new ArrayList<>(numHashTable); 
  
        for (int i = 0; i < numHashTable; i++) { 
            // 初始化哈希表 
            hashTable.add(null); 
        } 
    } 
  
    private int getBucketInd(K key) 
    { 
  
        // Using the inbuilt function from the object class 
        int hashCode = key.hashCode(); 
  
        // array index = hashCode%numHashTable 
        return (hashCode % numHashTable); 
    } 
  
    public void insert(K key, V value) 
    { 
        // 获取插入的关键字 key 的哈希值
        int bucketInd = getBucketInd(key); 
  
        MapNode<K, V> head = hashTable.get(bucketInd); 
  
        //插入 K-V
        while (head != null) { 
            if (head.key.equals(key)) { 
                head.value = value; 
                return; 
            } 
            head = head.next; 
        } 
   
        MapNode<K, V> newElementNode = new MapNode<K, V>(key, value); 
 
        head = hashTable.get(bucketInd); 

        newElementNode.next = head; 
  
        hashTable.set(bucketInd, newElementNode); 
 
        size++; 
  
        // 计算当前的装填因子 
        double loadFactor = (1.0 * size) / numHashTable; 
  
        // 装填因子 > 0.75，执行再哈希
        if (loadFactor > DEFAULT_LOAD_FACTOR) {  
            rehash(); 
        } 
    } 
  
    private void rehash() 
    { 
  
        System.out.println("\n***Rehashing Started***\n"); 
  
        // 保存原始哈希表
        ArrayList<MapNode<K, V> > temp = hashTable; 
  
        //创建新的数组（原始数组的两倍）
        hashTable = new ArrayList<MapNode<K, V> >(2 * numHashTable); 
  
        for (int i = 0; i < 2 * numHashTable; i++) {  
            buckets.add(null); 
        } 
        // 将旧数组中数据拷贝到新数组中
        size = 0; 
        numHashTable *= 2; 
  
        for (int i = 0; i < temp.size(); i++) { 
            MapNode<K, V> head = temp.get(i); 
  
            while (head != null) { 
                K key = head.key; 
                V val = head.value; 
 
                insert(key, val); 
                head = head.next; 
            } 
        }  
    } 
  
    public void printMap() 
    { 
        ArrayList<MapNode<K, V> > temp = hashTable; 
  
        System.out.println("当前的哈希表:"); 
        for (int i = 0; i < temp.size(); i++) { 
            // 获取哈希表当前 i 的头结点
            MapNode<K, V> head = temp.get(i); 
  
            while (head != null) { 
                System.out.println("key = " + head.key + ", 
                                   val = " + head.value); 
  
                head = head.next; 
            } 
        } 
        System.out.println(); 
    } 
} 
  
public class Rehashing { 
  
    public static void main(String[] args) 
    { 
  
        // 创建一个哈希表 
        Map<Integer, String> map = new Map<Integer, String>(); 
  
        // 插入元素[<50, "I">, <700, "Love">, <76, "Data">, 
        //<85, "Structure">, <92, "and">, <73, "Jing">, <101, "Yu">]
        map.insert(50, "I"); 
        map.printMap(); 
  
        map.insert(700, "Love"); 
        map.printMap(); 
  
        map.insert(76, "Data"); 
        map.printMap(); 
  
        map.insert(85, "Structure"); 
        map.printMap(); 
  
        map.insert(92, "and"); 
        map.printMap(); 

        map.insert(73, "Jing"); 
        map.printMap(); 

        map.insert(101, "Yu"); 
        map.printMap(); 
    } 
}