哈希表 06 时间复杂度分析 & 动态扩容

哈希表的时间复杂度分析

• n 个元素平均的分布在 M 棵红黑树中，每棵红黑树容纳的元素平均为 n/M ，即现有的哈希表的时间复杂度为 O(log(n/M))；
• 说好的 O(1) 呢？
• M 越大，元素分散的越平均，时间复杂度越低，M 足够大，时间复杂度理论上就可以达到 O(1)；

动态扩容代码

• 触发扩容，缩容的上界和哈希表的初始容量；

private static final int upperTol = 10;
private static final int lowerTol = 2;
private static final int initCapacity = 7;

public HashTable(){
    this(initCapacity);
}

• 添加元素时扩容

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)
            resize(2 * M);
    }
}

• 删除元素时缩容

public V remove(K key){
    V ret = null;
    TreeMap<K, V> map = hashtable[hash(key)];
    if(map.containsKey(key)){
        ret = map.remove(key);
        size --;

        if(size < lowerTol * M && M / 2 >= initCapacity)
            resize(M / 2);
    }
    return ret;
}

• 容量调整代码
  • 复制时的遍历，遍历的是老哈希表，老的M值要先存下来；
  • 复制的时候元素的key值重新计算hash值要用新的M值，要将this.M更新过来；

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;
    this.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;
}

速度比较

import java.util.ArrayList;

public class Main {

    public static void main(String[] args) {
        System.out.println("Pride and Prejudice");
        ArrayList<String> words = new ArrayList<>();
        if(FileOperation.readFile("pride-and-prejudice.txt", words)) {
            System.out.println("Total words: " + words.size());

            // Test BST
            long startTime = System.nanoTime();

            BST<String, Integer> bst = new BST<>();
            for (String word : words) {
                if (bst.contains(word))
                    bst.set(word, bst.get(word) + 1);
                else
                    bst.add(word, 1);
            }

            for(String word: words)
                bst.contains(word);

            long endTime = System.nanoTime();
            double time = (endTime - startTime) / 1000000000.0;
            System.out.println("BST: " + time + " s");


            // Test AVL
            startTime = System.nanoTime();

            AVLTree<String, Integer> avl = new AVLTree<>();
            for (String word : words) {
                if (avl.contains(word))
                    avl.set(word, avl.get(word) + 1);
                else
                    avl.add(word, 1);
            }

            for(String word: words)
                avl.contains(word);

            endTime = System.nanoTime();
            time = (endTime - startTime) / 1000000000.0;
            System.out.println("AVL: " + time + " s");


            // Test RBTree
            startTime = System.nanoTime();

            RBTree<String, Integer> rbt = new RBTree<>();
            for (String word : words) {
                if (rbt.contains(word))
                    rbt.set(word, rbt.get(word) + 1);
                else
                    rbt.add(word, 1);
            }

            for(String word: words)
                rbt.contains(word);

            endTime = System.nanoTime();
            time = (endTime - startTime) / 1000000000.0;
            System.out.println("RBTree: " + time + " s");


            // Test HashTable
            startTime = System.nanoTime();

            HashTable<String, Integer> ht = new HashTable<>();
            //HashTable<String, Integer> ht = new HashTable<>(131071);
            for (String word : words) {
                if (ht.contains(word))
                    ht.set(word, ht.get(word) + 1);
                else
                    ht.add(word, 1);
            }

            for(String word: words)
                ht.contains(word);

            endTime = System.nanoTime();
            time = (endTime - startTime) / 1000000000.0;
            System.out.println("HashTable: " + time + " s");
        }

        System.out.println();
    }
}

输出：

• 哈希表还是要快一点的；

Pride and Prejudice
Total words: 125901
BST: 0.1321059 s
AVL: 0.1091658 s
RBTree: 0.107052 s
HashTable: 0.1011918 s