注意观察0，4，8三个元素节点，在扩容前(对4取模)都位于下标0插槽；扩容后，数组容量翻倍(对8取模)，存在两种情况，0，8两个元素哈希值依然映射在下标0插槽(低位插槽)，而元素4则被映射到了下标4插槽(高位插槽)(当前下标(0) + 扩容前内部数组长度大小(4))。

　　通过遍历每个插槽，将内部元素按顺序进行rehash，得到扩容两倍后的哈希表(数据保留了之前的顺序，即先插入的节点依然位于桶链表靠前的位置)。

　　和向量扩容一样，虽然rehash操作的时间复杂度为O(n)。但是由于只在插入时偶尔的被触发，总体上看，rehash操作的时间复杂度为O(1)。

哈希表扩容前:

哈希表扩容后:

?

　　/**
     * 哈希表扩容
     *  reHash(){
        :::扩容两倍
        EntryNode<K,V>[] newElements = new EntryNode[this.elements.length * REHASH_BASE];

        :::遍历所有的插槽
        for (int i=0; i<this.elements.length; i++) {
            :::为单个插槽内的元素 rehash
            reHashSlot(i,newElements);
        }

        :::内部数组 ---> 扩容之后的新数组
        this.elements = newElements;
    }

    
     * 单个插槽内的数据进行rehash
     * void reHashSlot(int index,1)">[] newElements){
        :::获得当前插槽第一个元素
        EntryNode<K,V> currentEntryNode = .elements[index];
        if(currentEntryNode == :::当前插槽为空，直接返回
            :::低位桶链表 头部节点、尾部节点
        EntryNode<K,V> lowListHead = ;
        EntryNode<K,V> lowListTail = :::高位桶链表 头部节点、尾部节点
        EntryNode<K,V> highListHead = ;

        while(currentEntryNode != :::获得当前节点 在新数组中映射的插槽下标
            int entryNodeIndex = getIndex(currentEntryNode.key,newElements);
            :::是否和当前插槽下标相等
            if(entryNodeIndex == index){
                :::和当前插槽下标相等
                if(lowListHead == ){
                    :::初始化低位链表
                    lowListHead = currentEntryNode;
                    lowListTail = currentEntryNode;
                }{
                    :::在低位链表尾部拓展新的节点
                    lowListTail.next = lowListTail.next;
                }
            }:::和当前插槽下标不相等
                if(highListHead == :::初始化高位链表
                    highListHead = currentEntryNode;
                    highListTail =:::在高位链表尾部拓展新的节点
                    highListTail.next = highListTail.next;
                }
            }
            :::指向当前插槽的下一个节点
            currentEntryNode = currentEntryNode.next;
        }

        :::新扩容elements(index)插槽 存放lowList
        newElements[index] = lowListHead;
        :::lowList末尾截断
        if(lowListTail != ){
            lowListTail.next = :::新扩容elements(index + this.elements.length)插槽 存放highList
        newElements[index + this.elements.length] = highListHead;
        :::highList末尾截断
        if(highListTail != ){
            highListTail.next = ;
        }
    }

    
     * 判断是否需要 扩容
     *  needReHash(){
        return ((this.size / this.elements.length) > .loadFactor);
    }

3.6 其它接口实现：

 containsKey(K key) {
        V value = get(key);
        return (value != );
    }

    @Override
     containsValue(V value) {
        :::遍历全部桶链表
        for (EntryNode<K,V> element : .elements) {
            :::获得当前桶链表第一个节点
            EntryNode<K,V> entryNode = element;

            :::遍历当前桶链表
            while (entryNode != ) {
                :::如果value匹配
                 (entryNode.value.equals(value)) {
                    :::返回true
                    ;
                }  {
                    :::不匹配，指向下一个节点
                    entryNode = entryNode.next;
                }
            }
        }
        :::所有的节点都遍历了，没有匹配的value
        ;
    }

    @Override
     size() {
        .size;
    }

    @Override
     isEmpty() {
        return (this.size == 0 clear() {
        :::遍历内部数组，将所有桶链表全部清空
        for(this.elements[i] = :::size设置为0
        public Iterator<EntryNode<K,1)"> iterator() {
         Itr();
    }

    @Override
     String toString() {
        Iterator<EntryNode<K,V>> iterator = .iterator();

        :::空容器
        if(!iterator.hasNext()){
            return "[]":::容器起始使用"["
        StringBuilder s = new StringBuilder("[");

        :::反复迭代
        while(:::获得迭代的当前元素
            EntryNode<K,V> data = iterator.next();

            :::判断当前元素是否是最后一个元素
            iterator.hasNext()){
                :::是最后一个元素，用"]"收尾
                s.append(data).append("]");
                :::返回 拼接完毕的字符串
                 s.toString();
            }:::不是最后一个元素
                :::使用","分割，拼接到后面
                s.append(data).append(",");
            }
        }
    }

4.哈希表迭代器

　　1. 由于哈希表中数据分布不是连续的，所以在迭代器的初始化过程中必须先跳转到第一个非空数据节点，以避免无效的迭代。

（编辑：核心网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!