自己动手实现java数据结构（五）哈希表

　　因此getIndex方法的时间复杂度为O(1)。

   
     * 通过key的hashCode获得对应的内部数组下标
     *  key 传入的键值key
     *  对应的内部数组下标
     *  getIndex(K key){
        return getIndex(key,1)">.elements);
    }

    
     * 通过key的hashCode获得对应的内部数组插槽slot下标
     *  elements 内部数组
     * int getIndex(K key,EntryNode<K,1)">[] elements){
        ){
            ::: null 默认存储在第0个桶内
            return 0;
        }{
            int hashCode = key.hashCode();

            :::通过 高位和低位的异或运算，获得最终的hash映射，减少碰撞的几率
            int finalHashCode = hashCode ^ (hashCode >>> 16);
            return (elements.length-1) & finalHashCode;
        }
    }

3.3 链表查询方法：

　　当出现hash冲突时，会在对应插槽处生成一个单链表。我们需要提供一个方便的单链表查询方法，将增删改查接口的部分公用逻辑抽象出来，简化代码的复杂度。

　　值得注意的是：在判断Key值是否相等时使用的是EntryNode.keyIsEquals方法，内部最终是通过equals方法进行比较的。也就是说，判断key值是否相等和其它数据结构一样，依然是由equals方法决定的。hashCode方法的作用仅仅是使我们能够更快的定位到所映射的插槽处，加快查询效率。

　　思考一下，为什么要求在重写equals方法的同时，也应该重写hashCode方法？

   
     * 获得目标节点的前一个节点
     *  currentNode 当前桶链表节点
     *  key         对应的key
     *   返回当前桶链表中"匹配key的目标节点"的"前一个节点"
     *          注意：当桶链表中不存在匹配节点时，返回桶链表的最后一个节点
     *  currentNode,K key){
        :::不匹配
        EntryNode<K,V> nextNode = currentNode.next;
        :::遍历当前桶后面的所有节点
        while(nextNode != :::如果下一个节点的key匹配
            if(nextNode.keyIsEquals(key)){
                 currentNode;
            }:::不断指向下一个节点
                currentNode = nextNode;
                nextNode = nextNode.next;
            }
        }
        :::到达了桶链表的末尾，返回最后一个节点
         currentNode;
    }

3.4 增删改查接口：

　　哈希表的增删改查接口都是通过hash值直接计算出对应的插槽下标(getIndex方法)，然后遍历插槽内的桶链表进行进一步的精确查询(getTargetPreviousEntryNode方法)。在负载因子位于正常范围内时(一般小于1)，桶链表的平均长度非常短，可以认为单个桶链表的遍历查询时间复杂度为(O(1))。

　　因此哈希表的增删改查接口的时间复杂度都是O(1)。

    @Override
     V put(K key,V value) {
        (needReHash()){
            reHash();
        }

        :::获得对应的内部数组下标
        int index = getIndex(key);
        :::获得对应桶内的第一个节点
        EntryNode<K,V> firstEntryNode = .elements[index];

        :::如果当前桶内不存在任何节点
        if(firstEntryNode == :::创建一个新的节点
            this.elements[index] = new EntryNode<>(key,value);
            :::创建了新节点，size加1
            this.size++;
            ;
        }

        (firstEntryNode.keyIsEquals(key)){
            :::当前第一个节点的key与之匹配
            V oldValue = firstEntryNode.value;
            firstEntryNode.value = value;
             oldValue;
        }:::不匹配

            :::获得匹配的目标节点的前一个节点
            EntryNode<K,V> targetPreviousNode = getTargetPreviousEntryNode(firstEntryNode,key);
            :::获得匹配的目标节点
            EntryNode<K,V> targetNode = targetPreviousNode.next;
            if(targetNode != :::更新value的值
                V oldValue = targetNode.value;
                targetNode.value = value;
                 oldValue;
            }:::在桶链表的末尾 新增一个节点
                targetPreviousNode.next = :::创建了新节点，size加1
                ;
                ;
            }
        }
    }

    @Override
     V remove(K key) {
        ;
        }
        :::当前第一个节点的key与之匹配

            :::将桶链表的第一个节点指向后一个节点(兼容next为null的情况)
            this.elements[index] = firstEntryNode.next;
            :::移除了一个节点 size减一
            this.size--:::返回之前的value值
             firstEntryNode.value;
        } targetPreviousNode.next;

            :::将"前一个节点的next" 指向 "目标节点的next" ---> 相当于将目标节点从桶链表移除
                targetPreviousNode.next = targetNode.next;
                :::移除了一个节点 size减一
                 targetNode.value;
            }:::如果目标节点为空，说明key并不存在于哈希表中
                 V get(K key) {
        :::当前第一个节点的key与之匹配
            ;
            }
        }
    }

3.5 扩容rehash操作：

　　前面提到，当插入数据时发现哈希表过于拥挤，超过了负载因子指定的值时，会触发一次rehash扩容操作。

　　扩容时，我们的内部数组扩容了2倍，所以对于每一个插槽内的元素在rehash时存在两种可能：

　　　　1.依然映射到当前下标插槽处

　　　　2.映射到高位下标处(当前下标 + 扩容前内部数组长度大小)

（编辑：核心网）

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