1.整型哈希函數(shù)的設計
小范圍正整數(shù)直接使用
小范圍負整數(shù)整體進行偏移
大整數(shù)，通常做法是"模一個素數(shù)"

2.浮點型哈希函數(shù)的設計
轉(zhuǎn)成整型進行處理

3.字符串哈希函數(shù)的設計
轉(zhuǎn)成整型進行處理

image.png

簡單變形優(yōu)化

image.png

image.png

image.png

復合類型哈希函數(shù)的設計
轉(zhuǎn)成整型進行處理

image.png

哈希函數(shù)的設計原則

image.png

哈希沖突的處理
鏈地址法

image.png

開放地址法之線性探測

image.png

開放地址法之平方探測

image.png

開放地址法之二次哈希

image.png

哈希表的動態(tài)空間處理

image.png

實現(xiàn)哈希表的業(yè)務邏輯

import java.util.TreeMap;

public class HashTable<K, V> {

    private final int[] capacity
            = {53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
            49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917,
            25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741};
    private static final int upperTol = 10;
    private static final int lowerTol = 2;
    private int capacityIndex = 0;
    private TreeMap<K, V>[] hashTable;
    private int M;
    private int size;

    public HashTable() {

        this.M = capacity[capacityIndex];
        this.size = 0;
        hashTable = new TreeMap[M];
        for (int i = 0; i < M; i++) {
            hashTable[i] = new TreeMap<>();
        }
    }

    private int hash(K key) {
        return key.hashCode() & 0x7fffffff % M;
    }

    public void add(K key, V value) {

        TreeMap<K, V> map = hashTable[hash(key)];

        if (map.containsKey(key)) {
            map.put(key, value);
        } else {
            map.put(key, value);
            size++;
            if (size >= upperTol * M && capacityIndex + 1 < capacity.length) {
                capacityIndex++;
                resize(capacity[capacityIndex]);
            }
        }
    }

    public V remove(K key) {

        TreeMap<K, V> map = hashTable[hash(key)];

        V ret = null;
        if (map.containsKey(key)) {
            ret = map.remove(key);
            size--;
            if (size < lowerTol * M && capacityIndex - 1 >= 0) {
                capacityIndex--;
                resize(capacity[capacityIndex]);
            }
        }
        return ret;
    }

    public void set(K key, V value) {

        TreeMap<K, V> map = hashTable[hash(key)];

        if (!map.containsKey(key)) {
            throw new IllegalArgumentException(key + "doesn't exist.");
        } else {
            map.put(key, value);
        }
    }

    public boolean contains(K key) {

        return hashTable[hash(key)].containsKey(key);
    }

    public V get(K key) {

        return hashTable[hash(key)].get(key);
    }

    private void resize(int newM) {

        TreeMap<K, V>[] newHashTable = new TreeMap[newM];
        for (int i = 0; i < newM; i++) {
            newHashTable[i] = new TreeMap<>();
        }

        int oldM = M;
        M = newM;
        for (int i = 0; i < oldM; i++) {
            TreeMap<K, V> map = hashTable[i];
            for (K key : map.keySet()) {
                newHashTable[hash(key)].put(key, map.get(key));
            }
        }

        this.hashTable = newHashTable;
    }

}