本身着手完成java数据结构(五)哈希表_玖富娱乐


玖富娱乐是一家为代理招商,直属主管信息发布为主的资讯网站,同时也兼顾玖富娱乐代理注册登录地址。

1.哈希表引见

  前面我们已引见了很多范例的数据组织。在想要查询容器内特定元素时,有序向量使得我们能运用二分查找法举行准确的查询((O(logN)对数庞杂度,很高效)。
  可人类老是不知知足,依旧在追求一种更高效的特定元素查询的数据组织,哈希表/散列表(hash table)就应运而生啦。哈希表在特定元素的插进去,删除和查询时都可以或许抵达O(1)常数的时候庞杂度,非常高效。

1.1 哈希算法

  哈希算法的界说:把恣意长度的输入经由过程哈希算法转换映照为流动长度的输出,所取得的输出被称为哈希值(hashCode = hash(input))。哈希映照是一种多对一的干系,即多个分歧的输入有可以或许对应着一个雷同的哈希值输出;也意味着,哈希映照是不可逆,没法复原的。

  举个例子:我们有一个好朋友叫熊大,人人都叫他老熊。可以或许明白为是一个hash算法:关于一小我名,我们一样平常称谓为"老" 姓氏(单姓) (hash(熊大) = 老熊)。同时,我们另有一个好朋友叫熊二,我们也叫他老熊(hash(熊二) = 老熊)。当熊大和熊二两个好朋友同时和我们聚首时,都称谓他们为老熊就不太适宜啦,因为这时候涌现了hash争执。老熊这个称谓同时对应了多小我,多个分歧的输入对应了雷同的哈希值输出。

  java在Object这一最高层工具中完成了hashCode要领,并许可子类重写更顺应本身,争执概率更低的hashCode要领。

1.2 哈希表完成的基础思路

  哈希表存储的是key-value键值对组织的数据,其基础是一个数组。

  因为接纳hash算法会涌现hash争执,一个数组下标对应了多个元素。罕见的处理hash争执的要领有:开放地点法、从新哈希法、拉链法等等,我们的哈希表完成接纳的是拉链法处理hash争执。

  接纳拉链法的哈希表将内部数组的每一个元素视为一个插槽(slot)或许桶(bucket),并将数据寄存在键值对节点(EntryNode)中。EntryNode除寄存key和value,还保护着一个next节点的援用。为了处理hash争执,单个插槽内的多个EntryNode组成一个简朴的单向链表,插槽指向链表的头部节点,新的数据将会插进去以后链表的尾部。

  key值分歧但映照的hash值雷同的元素在哈希表的同一个插槽中以链表的情势共存。

  

1.3 哈希表的负载因子(loadFactor):

  哈希表在查询数据时经由过程直接盘算数据hash值对应的插槽,敏捷猎取到key值对应的数据,举行非常高效的数据查询。

  但依旧存在一个题目:虽然设想优越的hash函数可以或许尽量的下降hash争执的概率,但hash争执照样不可制止的。当发作频仍的哈希争执时,对应的插槽内可以或许会寄存较多的元素,致使插槽内的链表数据过量。而链表的查询效力是非常低的,在极度状况下,甚至会涌现一切元素都映照寄存在同一个插槽内,此时的哈希表退步成了一个链表,查询效力急剧下降。

  一样平常的,哈希表存储的数据量一准时,内部数组的巨细和数组插槽指向的链表长度成反比。换句话说,总数据量肯定,内部数组的容量越大(插槽越多),均匀下来桶链表的长度也就越小,查询效力越高。

  一致数据量下,哈希表内部数组容量越大,查询效力越高,但同时空间占用也越高,这本质上是一个空间换时候的弃取。

  哈希表许可用户在初始化时指定负载因子(loadFactor):负载因子代表着存储的总数据量内部数组巨细比值。插进去新数据时,推断哈希表以后的存储量和内部数组的比值是不是凌驾了负载因子。当比值凌驾了负载因子时,哈希表以为内部过于拥堵,查询效力太低,会触发一次扩容的rehash操纵。rehash会对内部数组扩容,将存储的元素从新举行hash映照,使得哈希表始终保持一个适宜的查询效力。

  经由过程指定自界说的负载因子,用户可以或许掌握哈希表在空间和时候上弃取的水平,使哈希表能更有用地顺应用户的运用场景。

  指定的负载因子越大,哈希表越拥堵(负载高,紧凑),查询效力越低,空间效力越高。

  指定的负载因子越小,哈希表越希罕(负载小,松懈),查询效力越高,空间效力越低。

2.哈希表ADT接口

  和之前引见的链表分歧,我们在哈希表的ADT接口中袒露出了哈希表内部完成的EntryNode键值对节点。经由过程袒露进来的public要领,用户在运用哈希表时,可以或许取得内部的键值对节点,天真的接见个中的key、value数据(但没有袒露setKey要领,不许可用户本身设置key值)。

public interface Map <K,V>{
    /**
     * 存入键值对
     * @param key   key值
     * @param value value
     * @return 被掩盖的的value值
     */
    V put(K key,V value);

    /**
     * 移除键值对
     * @param key   key值
     * @return 被删除的value的值
     */
    V remove(K key);

    /**
     * 猎取key对应的value值
     * @param key   key值
     * @return      对应的value值
     */
    V get(K key);

    /**
     * 是不是包罗以后key值
     * @param key   key值
     * @return      true:包罗 false:不包罗
     */
    boolean containsKey(K key);

    /**
     * 是不是包罗以后value值
     * @param value   value值
     * @return        true:包罗 false:不包罗
     */
    boolean containsValue(V value);

    /**
     * 取得以后map存储的键值对数目
     * @return 键值对数目
     * */
    int size();

    /**
     * 以后map是不是为空
     * @return  true:为空 false:不为空
     */
    boolean isEmpty();

    /**
     * 清空以后map
     */
    void clear();

    /**
     * 取得迭代器
     * @return 迭代器工具
     */
    Iterator<EntryNode<K,V>> iterator();

    /**
     * 键值对节点 内部类
     * */
    class EntryNode<K,V>{
        final K key;
        V value;
        EntryNode<K,V> next;

        EntryNode(K key, V value) {
            this.key = key;
            this.value = value;
        }

        boolean keyIsEquals(K key){
            if(this.key == key){
                return true;
            }

            if(key == null){
                //:::若是走到这步,this.key不等于null,不婚配
                return false;
            }else{
                return key.equals(this.key);
            }
        }

        EntryNode<K, V> getNext() {
            return next;
        }

        void setNext(EntryNode<K, V> next) {
            this.next = next;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        public void setValue(V value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return key   "="   value;
        }
    }
}

3.哈希表完成细节

3.1 哈希表基础属性:      

public class HashMap<K,V> implements Map<K,V>{

    /**
     * 内部数组
     * */
    private EntryNode<K,V>[] elements;

    /**
     * 以后哈希表的巨细
     * */
    private int size;

    /**
     * 负载因子
     * */
    private float loadFactor;

    /**
     * 默许的哈希表容量
     * */
    private final static int DEFAULT_CAPACITY = 16;

    /**
     * 扩容翻倍的基数
     * */
    private final static int REHASH_BASE = 2;

    /**
     * 默许的负载因子
     * */
    private final static float DEFAULT_LOAD_FACTOR = 0.75f;

    //========================================组织要领===================================================
    /**
     * 默许组织要领
     * */
    @SuppressWarnings("unchecked")
    public HashMap() {
        this.size = 0;
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        elements = new EntryNode[DEFAULT_CAPACITY];
    }

    /**
     * 指定初始容量的组织要领
     * @param capacity 指定的初始容量
     * */
    @SuppressWarnings("unchecked")
    public HashMap(int capacity) {
        this.size = 0;
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        elements = new EntryNode[capacity];
    }

    /**
     * 指定初始容量和负载因子的组织要领
     * @param capacity 指定的初始容量
     * @param loadFactor 指定的负载因子
     * */
    @SuppressWarnings("unchecked")
    public HashMap(int capacity,int loadFactor) {
        this.size = 0;
        this.loadFactor = loadFactor;
        elements = new EntryNode[capacity];
    }
}

3.2 经由过程hash值猎取对应插槽下标:

  猎取hash的要领仅和数据本身有关,不遭到哈希表存储数据量的影响。

  因此getIndex要领的时候庞杂度为O(1)

   /**
     * 经由过程key的hashCode取得对应的内部数组下标
     * @param key 传入的键值key
     * @return 对应的内部数组下标
     * */
    private int getIndex(K key){
        return getIndex(key,this.elements);
    }

    /**
     * 经由过程key的hashCode取得对应的内部数组插槽slot下标
     * @param key 传入的键值key
     * @param elements 内部数组
     * @return 对应的内部数组下标
     * */
    private int getIndex(K key,EntryNode<K,V>[] elements){
        if(key == null){
            //::: null 默许存储在第0个桶内
            return 0;
        }else{
            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要领?

   /**
     * 取得目的节点的前一个节点
     * @param currentNode 以后桶链表节点
     * @param key         对应的key
     * @return  返回以后桶链表中"婚配key的目的节点"的"前一个节点"
     *          注重:当桶链表中不存在婚配节点时,返回桶链表的末了一个节点
     * */
    private EntryNode<K,V> getTargetPreviousEntryNode(EntryNode<K,V> currentNode,K key){
        //:::不婚配
        EntryNode<K,V> nextNode = currentNode.next;
        //:::遍历以后桶背面的一切节点
        while(nextNode != null){
            //:::若是下一个节点的key婚配
            if(nextNode.keyIsEquals(key)){
                return currentNode;
            }else{
                //:::赓续指向下一个节点
                currentNode = nextNode;
                nextNode = nextNode.next;
            }
        }
        //:::抵达了桶链表的末端,返回末了一个节点
        return currentNode;
    }

3.4 增编削查接口:

  哈希表的增编削查接口都是经由过程hash值直接盘算出对应的插槽下标(getIndex要领),然后遍历插槽内的桶链表举行进一步的准确查询(getTargetPreviousEntryNode要领)。在负载因子位于一般范围内时(一样平常小于1),桶链表的均匀长度非常短,可以或许以为单个桶链表的遍历查询时候庞杂度为(O(1))

  因此哈希表的增编削查接口时候庞杂度都是O(1)

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

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

        //:::若是以后桶内不存在任何节点
        if(firstEntryNode == null){
            //:::建立一个新的节点
            this.elements[index] = new EntryNode<>(key,value);
            //:::建立了新节点,size加1
            this.size  ;
            return null;
        }

        if(firstEntryNode.keyIsEquals(key)){
            //:::以后第一个节点的key与之婚配
            V oldValue = firstEntryNode.value;
            firstEntryNode.value = value;
            return oldValue;
        }else{
            //:::不婚配

            //:::取得婚配的目的节点的前一个节点
            EntryNode<K,V> targetPreviousNode = getTargetPreviousEntryNode(firstEntryNode,key);
            //:::取得婚配的目的节点
            EntryNode<K,V> targetNode = targetPreviousNode.next;
            if(targetNode != null){
                //:::更新value的值
                V oldValue = targetNode.value;
                targetNode.value = value;
                return oldValue;
            }else{
                //:::在桶链表的末端 新增一个节点
                targetPreviousNode.next = new EntryNode<>(key,value);
                //:::建立了新节点,size加1
                this.size  ;
                return null;
            }
        }
    }

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

        //:::若是以后桶内不存在任何节点
        if(firstEntryNode == null){
            return null;
        }
        if(firstEntryNode.keyIsEquals(key)){
            //:::以后第一个节点的key与之婚配

            //:::将桶链表的第一个节点指向后一个节点(兼容next为null的状况)
            this.elements[index] = firstEntryNode.next;
            //:::移除一个节点 size减一
            this.size--;
            //:::返回之前的value值
            return firstEntryNode.value;
        }else{
            //:::不婚配

            //:::取得婚配的目的节点的前一个节点
            EntryNode<K,V> targetPreviousNode = getTargetPreviousEntryNode(firstEntryNode,key);
            //:::取得婚配的目的节点
            EntryNode<K,V> targetNode = targetPreviousNode.next;

            if(targetNode != null){
                //:::将"前一个节点的next" 指向 "目的节点的next" ---> 相当于将目的节点从桶链表移除
                targetPreviousNode.next = targetNode.next;
                //:::移除一个节点 size减一
                this.size--;
                return targetNode.value;
            }else{
                //:::若是目的节点为空,申明key其实不存在于哈希表中
                return null;
            }
        }
    }

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

        //:::若是以后桶内不存在任何节点
        if(firstEntryNode == null){
            return null;
        }
        if(firstEntryNode.keyIsEquals(key)){
            //:::以后第一个节点的key与之婚配
            return firstEntryNode.value;
        }else{
            //:::取得婚配的目的节点的前一个节点
            EntryNode<K,V> targetPreviousNode = getTargetPreviousEntryNode(firstEntryNode,key);
            //:::取得婚配的目的节点
            EntryNode<K,V> targetNode = targetPreviousNode.next;

            if(targetNode != null){
                return targetNode.value;
            }else{
                //:::若是目的节点为空,申明key其实不存在于哈希表中
                return null;
            }
        }
    }

3.5 扩容rehash操纵:

  前面提到,当插进去数据时发明哈希表过于拥堵,凌驾了负载因子指定的值时,会触发一次rehash扩容操纵。

  扩容时,我们的内部数组扩容了2倍,以是关于每一个插槽内的元素在rehash时存在两种可以或许:

    1.依旧映照到以后下标插槽处

    2.映照到高位下标处(以后下标 扩容前内部数组长度巨细)

  注重视察0,4,8三个元素节点,在扩容前(对4取模)都位于下标0插槽;扩容后,数组容量翻倍(对8取模),存在两种状况,0,8两个元素哈希值依旧映照在下标0插槽(低位插槽),而元素4则被映照到了下标4插槽(高位插槽)(以后下标(0) 扩容前内部数组长度巨细(4))。

  经由过程遍历每一个插槽,将内部元素按递次举行rehash,取得扩容两倍后的哈希表(数据保留了之前的递次,即先插进去的节点依旧位于桶链表靠前的地位)。

  和向量扩容一样,虽然rehash操纵的时候庞杂度为O(n)。然则因为只在插进去时偶然的被触发,整体上看,rehash操纵的时候庞杂度为O(1)

哈希表扩容前:

-玖富娱乐是一家为代理招商,直属主管信息发布为主的资讯网站,同时也兼顾玖富娱乐代理注册登录地址。-

哈希表扩容后:

 

  /**
     * 哈希表扩容
     * */
    @SuppressWarnings("unchecked")
    private void 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
     * */
    private void reHashSlot(int index,EntryNode<K, V>[] newElements){
        //:::取得以后插槽第一个元素
        EntryNode<K, V> currentEntryNode = this.elements[index];
        if(currentEntryNode == null){
            //:::以后插槽为空,直接返回
            return;
        }

        //:::低位桶链表 头部节点、尾部节点
        EntryNode<K, V> lowListHead = null;
        EntryNode<K, V> lowListTail = null;
        //:::高位桶链表 头部节点、尾部节点
        EntryNode<K, V> highListHead = null;
        EntryNode<K, V> highListTail = null;

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

        //:::新扩容elements(index)插槽 寄存lowList
        newElements[index] = lowListHead;
        //:::lowList末端截断
        if(lowListTail != null){
            lowListTail.next = null;
        }

        //:::新扩容elements(index   this.elements.length)插槽 寄存highList
        newElements[index   this.elements.length] = highListHead;
        //:::highList末端截断
        if(highListTail != null){
            highListTail.next = null;
        }
    }

    /**
     * 推断是不是须要 扩容
     * */
    private boolean needReHash(){
        return ((this.size / this.elements.length) > this.loadFactor);
    }

3.6 别的接口完成:

    @Override
    public boolean containsKey(K key) {
        V value = get(key);
        return (value != null);
    }

    @Override
    public boolean containsValue(V value) {
        //:::遍历悉数桶链表
        for (EntryNode<K, V> element : this.elements) {
            //:::取得以后桶链表第一个节点
            EntryNode<K, V> entryNode = element;

            //:::遍历以后桶链表
            while (entryNode != null) {
                //:::若是value婚配
                if (entryNode.value.equals(value)) {
                    //:::返回true
                    return true;
                } else {
                    //:::不婚配,指向下一个节点
                    entryNode = entryNode.next;
                }
            }
        }
        //:::一切的节点都遍历了,没有婚配的value
        return false;
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public boolean isEmpty() {
        return (this.size == 0);
    }

    @Override
    public void clear() {
        //:::遍历内部数组,将一切桶链表悉数清空
        for(int i=0; i<this.elements.length; i  ){
            this.elements[i] = null;
        }

        //:::size设置为0
        this.size = 0;
    }

    @Override
    public Iterator<EntryNode<K,V>> iterator() {
        return new Itr();
    }

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

        //:::空容器
        if(!iterator.hasNext()){
            return "[]";
        }

        //:::容器肇端运用"["
        StringBuilder s = new StringBuilder("[");

        //:::重复迭代
        while(true){
            //:::取得迭代的以后元素
            EntryNode<K,V> data = iterator.next();

            //:::推断以后元素是不是是末了一个元素
            if(!iterator.hasNext()){
                //:::是末了一个元素,用"]"扫尾
                s.append(data).append("]");
                //:::返回 拼接终了的字符串
                return s.toString();
            }else{
                //:::不是末了一个元素
                //:::运用", "支解,拼接到背面
                s.append(data).append(", ");
            }
        }
    }

4.哈希表迭代器

  1. 因为哈希表中数据散布不是一连的,以是在迭代器的初始化过程当中必需先跳转到第一个非空数据节点,以制止无效的迭代。

  2. 当迭代器的下标抵达以后插槽链表的末端时,迭代器下标须要跳转到靠后插槽的第一个非空数据节点。

  /**
     * 哈希表 迭代器完成
     */
    private class Itr implements Iterator<EntryNode<K,V>> {
        /**
         * 迭代器 以后节点
         * */
        private EntryNode<K,V> currentNode;

        /**
         * 迭代器 下一个节点
         * */
        private EntryNode<K,V> nextNode;

        /**
         * 迭代器 以后内部数组的下标
         * */
        private int currentIndex;

        /**
         * 默许组织要领
         * */
        private Itr(){
            //:::若是以后哈希表为空,直接返回
            if(HashMap.this.isEmpty()){
                return;
            }
            //:::在组织要领中,将迭代器下标移动到第一个有用的节点上

            //:::遍历内部数组,找到第一个不为空的数组插槽slot
            for(int i=0; i<HashMap.this.elements.length; i  ){
                //:::设置以后index
                this.currentIndex = i;

                EntryNode<K,V> firstEntryNode = HashMap.this.elements[i];
                //:::找到了第一个不为空的插槽slot
                if(firstEntryNode != null){
                    //:::nextNode = 以后插槽第一个节点
                    this.nextNode = firstEntryNode;

                    //:::组织要领马上完毕
                    return;
                }
            }
        }

        @Override
        public boolean hasNext() {
            return (this.nextNode != null);
        }

        @Override
        public EntryNode<K,V> next() {
            this.currentNode = this.nextNode;
            //:::暂存须要返回的节点
            EntryNode<K,V> needReturn = this.nextNode;

            //:::nextNode指向本身的next
            this.nextNode = this.nextNode.next;
            //:::推断以后nextNode是不是为null
            if(this.nextNode == null){
                //:::申明以后地点的桶链表已遍历终了

                //:::寻觅下一个非空的插槽
                for(int i=this.currentIndex 1; i<HashMap.this.elements.length; i  ){
                    //:::设置以后index
                    this.currentIndex = i;

                    EntryNode<K,V> firstEntryNode = HashMap.this.elements[i];
                    //:::找到了后续不为空的插槽slot
                    if(firstEntryNode != null){
                        //:::nextNode = 以后插槽第一个节点
                        this.nextNode = firstEntryNode;
                        //:::跳出轮回
                        break;
                    }
                }
            }
            return needReturn;
        }

        @Override
        public void remove() {
            if(this.currentNode == null){
                throw new IteratorStateErrorException("迭代器状况非常: 可以或许在一次迭代中举行了屡次remove操纵");
            }

            //:::取得须要被移除的节点的key
            K currentKey = this.currentNode.key;
            //:::将其从哈希表中移除
            HashMap.this.remove(currentKey);

            //:::currentNode设置为null,防备重复挪用remove要领
            this.currentNode = null;
        }
    }

5.哈希表机能

5.1 空间效力:

  哈希表的空间效力很大水平上取决于负载因子。一般,为了包管哈希表查询的高效性,负载因子都设置的对照小(小于1),因此可以或许会涌现很多空的插槽,糟蹋空间。

  整体而言,哈希表的空间效力低于向量和链表。

5.2 时候效力:

  一样平常的,哈希表增编削查接口的时候庞杂度都是O(1)。然则涌现较多的hash争执时,争执范围内的key的增编削查效力较低,时候效力会有肯定的动摇。

  整体而言,哈希表的时候效力高于向量和链表。

  哈希表的时候效力很高,可天下没有免费的午饭,据统计,哈希表的空间利用率一般状况下还不到50%。

  哈希表是一个运用空间来调换时候的数据组织,对查询机能有较高请求的场所,可以或许斟酌运用哈希表。

6.哈希表总结

6.1 以后版本缺点

  至此,我们已完成了一个基础的哈希表,但还存在很多显着缺点:   

  1.当hash争执对照频仍时,查询效力急剧下降。

  jdk在1.8版本的哈希表完成(java.util.HashMap)中,对这一场景举行了优化。当内部桶链表的节点个数凌驾肯定数目(默以为8)时,会将插槽中的桶链表转换成一个红黑树(查询效力为O(logN))。

  2.不支持多线程

  在多线程的情况,并发的接见一个哈希表会致使诸如:扩容时内部节点死轮回、丧失插进去数据等非常状况。

6.2 查询特定元素的要领

  我们现在查询特定元素有几种分歧的要领:

  1.递次查找

  在无序向量或许链表中,查找一个特定元素是经由过程从头至尾遍历容器内元素的体式格局完成的,实行速率正比于数据量的巨细,递次查找的时候庞杂度为O(n),效力较低

  2.二分查找

  在有序向量和背面要引见的二叉搜刮树中,因为容器内部的元素是有序的,因此可以或许经由过程二分查找对照的体式格局查询特定的元素,二分查找的时候庞杂度为O(logN),效力较高。 

  3.哈希查找

  在哈希表中,经由过程直接盘算出数据hash值对应的插槽(slot)(时候庞杂度O(1)),查找出对应的数据,哈希查找的时候庞杂度为O(1),效力极高。

特定元素的查找体式格局和排序算法的干系

  1.递次查找对应冒泡排序挑选排序等,效力较低,时候庞杂度(O(n²))。

  2.二分查找对应疾速排序合并排序等,效力较高,时候庞杂度(O(nLogn))。

  3.哈希查找对应基排序,效力极高,时候庞杂度(O(n))。

  在大牛刘未鹏的博客中有越发细致的申明,http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick。

6.3 完全代码

哈希表ADT接口:

  1 public interface Map <K,V>{
  2     /**
  3      * 存入键值对
  4      * @param key   key值
  5      * @param value value
  6      * @return 被掩盖的的value值
  7      */
  8     V put(K key,V value);
  9 
 10     /**
 11      * 移除键值对
 12      * @param key   key值
 13      * @return 被删除的value的值
 14      */
 15     V remove(K key);
 16 
 17     /**
 18      * 猎取key对应的value值
 19      * @param key   key值
 20      * @return      对应的value值
 21      */
 22     V get(K key);
 23 
 24     /**
 25      * 是不是包罗以后key值
 26      * @param key   key值
 27      * @return      true:包罗 false:不包罗
 28      */
 29     boolean containsKey(K key);
 30 
 31     /**
 32      * 是不是包罗以后value值
 33      * @param value   value值
 34      * @return        true:包罗 false:不包罗
 35      */
 36     boolean containsValue(V value);
 37 
 38     /**
 39      * 取得以后map存储的键值对数目
 40      * @return 键值对数目
 41      * */
 42     int size();
 43 
 44     /**
 45      * 以后map是不是为空
 46      * @return  true:为空 false:不为空
 47      */
 48     boolean isEmpty();
 49 
 50     /**
 51      * 清空以后map
 52      */
 53     void clear();
 54 
 55     /**
 56      * 取得迭代器
 57      * @return 迭代器工具
 58      */
 59     Iterator<EntryNode<K,V>> iterator();
 60 
 61     /**
 62      * 键值对节点 内部类
 63      * */
 64     class EntryNode<K,V>{
 65         final K key;
 66         V value;
 67         EntryNode<K,V> next;
 68 
 69         EntryNode(K key, V value) {
 70             this.key = key;
 71             this.value = value;
 72         }
 73 
 74         boolean keyIsEquals(K key){
 75             if(this.key == key){
 76                 return true;
 77             }
 78 
 79             if(key == null){
 80                 //:::若是走到这步,this.key不等于null,不婚配
 81                 return false;
 82             }else{
 83                 return key.equals(this.key);
 84             }
 85         }
 86 
 87         EntryNode<K, V> getNext() {
 88             return next;
 89         }
 90 
 91         void setNext(EntryNode<K, V> next) {
 92             this.next = next;
 93         }
 94 
 95         public K getKey() {
 96             return key;
 97         }
 98 
 99         public V getValue() {
100             return value;
101         }
102 
103         public void setValue(V value) {
104             this.value = value;
105         }
106 
107         @Override
108         public String toString() {
109             return key   "="   value;
110         }
111     }
112 }
View Code

哈希表完成:

  1 public class HashMap<K,V> implements Map<K,V>{
  2 
  3     //===========================================成员属性================================================
  4     /**
  5      * 内部数组
  6      * */
  7     private EntryNode<K,V>[] elements;
  8 
  9     /**
 10      * 以后哈希表的巨细
 11      * */
 12     private int size;
 13 
 14     /**
 15      * 负载因子
 16      * */
 17     private float loadFactor;
 18 
 19     /**
 20      * 默许的哈希表容量
 21      * */
 22     private final static int DEFAULT_CAPACITY = 16;
 23 
 24     /**
 25      * 扩容翻倍的基数 两倍
 26      * */
 27     private final static int REHASH_BASE = 2;
 28 
 29     /**
 30      * 默许的负载因子
 31      * */
 32     private final static float DEFAULT_LOAD_FACTOR = 0.75f;
 33 
 34     //========================================组织要领===================================================
 35     /**
 36      * 默许组织要领
 37      * */
 38     @SuppressWarnings("unchecked")
 39     public HashMap() {
 40         this.size = 0;
 41         this.loadFactor = DEFAULT_LOAD_FACTOR;
 42         elements = new EntryNode[DEFAULT_CAPACITY];
 43     }
 44 
 45     /**
 46      * 指定初始容量的组织要领
 47      * @param capacity 指定的初始容量
 48      * */
 49     @SuppressWarnings("unchecked")
 50     public HashMap(int capacity) {
 51         this.size = 0;
 52         this.loadFactor = DEFAULT_LOAD_FACTOR;
 53         elements = new EntryNode[capacity];
 54     }
 55 
 56     /**
 57      * 指定初始容量和负载因子的组织要领
 58      * @param capacity 指定的初始容量
 59      * @param loadFactor 指定的负载因子
 60      * */
 61     @SuppressWarnings("unchecked")
 62     public HashMap(int capacity,int loadFactor) {
 63         this.size = 0;
 64         this.loadFactor = loadFactor;
 65         elements = new EntryNode[capacity];
 66     }
 67 
 68     //==========================================内部辅佐要领=============================================
 69     /**
 70      * 经由过程key的hashCode取得对应的内部数组下标
 71      * @param key 传入的键值key
 72      * @return 对应的内部数组下标
 73      * */
 74     private int getIndex(K key){
 75         return getIndex(key,this.elements);
 76     }
 77 
 78     /**
 79      * 经由过程key的hashCode取得对应的内部数组插槽slot下标
 80      * @param key 传入的键值key
 81      * @param elements 内部数组
 82      * @return 对应的内部数组下标
 83      * */
 84     private int getIndex(K key,EntryNode<K,V>[] elements){
 85         if(key == null){
 86             //::: null 默许存储在第0个桶内
 87             return 0;
 88         }else{
 89             int hashCode = key.hashCode();
 90 
 91             //:::经由过程 高位和低位的异或运算,取得终究的hash映照,削减碰撞的概率
 92             int finalHashCode = hashCode ^ (hashCode >>> 16);
 93             return (elements.length-1) & finalHashCode;
 94         }
 95     }
 96 
 97     /**
 98      * 取得目的节点的前一个节点
 99      * @param currentNode 以后桶链表节点
100      * @param key         对应的key
101      * @return 返回以后桶链表中"婚配key的目的节点"的"前一个节点"
102      *          注重:当桶链表中不存在婚配节点时,返回桶链表的末了一个节点
103      * */
104     private EntryNode<K,V> getTargetPreviousEntryNode(EntryNode<K,V> currentNode,K key){
105         //:::不婚配
106         EntryNode<K,V> nextNode = currentNode.next;
107         //:::遍历以后桶背面的一切节点
108         while(nextNode != null){
109             //:::若是下一个节点的key婚配
110             if(nextNode.keyIsEquals(key)){
111                 return currentNode;
112             }else{
113                 //:::赓续指向下一个节点
114                 currentNode = nextNode;
115                 nextNode = nextNode.next;
116             }
117         }
118 
119         //:::抵达了桶链表的末端,返回末了一个节点
120         return currentNode;
121     }
122 
123     /**
124      * 哈希表扩容
125      * */
126     @SuppressWarnings("unchecked")
127     private void reHash(){
128         //:::扩容两倍
129         EntryNode<K,V>[] newElements = new EntryNode[this.elements.length * REHASH_BASE];
130 
131         //:::遍历一切的插槽
132         for (int i=0; i<this.elements.length; i  ) {
133             //:::为单个插槽内的元素 rehash
134             reHashSlot(i,newElements);
135         }
136 
137         //:::内部数组 ---> 扩容以后的新数组
138         this.elements = newElements;
139     }
140 
141     /**
142      * 单个插槽内的数据举行rehash
143      * */
144     private void reHashSlot(int index,EntryNode<K, V>[] newElements){
145         //:::取得以后插槽第一个元素
146         EntryNode<K, V> currentEntryNode = this.elements[index];
147         if(currentEntryNode == null){
148             //:::以后插槽为空,直接返回
149             return;
150         }
151 
152         //:::低位桶链表 头部节点、尾部节点
153         EntryNode<K, V> lowListHead = null;
154         EntryNode<K, V> lowListTail = null;
155         //:::高位桶链表 头部节点、尾部节点
156         EntryNode<K, V> highListHead = null;
157         EntryNode<K, V> highListTail = null;
158 
159         while(currentEntryNode != null){
160             //:::取得以后节点 在新数组中映照的插槽下标
161             int entryNodeIndex = getIndex(currentEntryNode.key,newElements);
162             //:::是不是和以后插槽下标相称
163             if(entryNodeIndex == index){
164                 //:::和以后插槽下标相称
165                 if(lowListHead == null){
166                     //:::初始化低位链表
167                     lowListHead = currentEntryNode;
168                     lowListTail = currentEntryNode;
169                 }else{
170                     //:::在低位链表尾部拓展新的节点
171                     lowListTail.next = currentEntryNode;
172                     lowListTail = lowListTail.next;
173                 }
174             }else{
175                 //:::和以后插槽下标不相称
176                 if(highListHead == null){
177                     //:::初始化高位链表
178                     highListHead = currentEntryNode;
179                     highListTail = currentEntryNode;
180                 }else{
181                     //:::在高位链表尾部拓展新的节点
182                     highListTail.next = currentEntryNode;
183                     highListTail = highListTail.next;
184                 }
185             }
186             //:::指向以后插槽的下一个节点
187             currentEntryNode = currentEntryNode.next;
188         }
189 
190         //:::新扩容elements(index)插槽 寄存lowList
191         newElements[index] = lowListHead;
192         //:::lowList末端截断
193         if(lowListTail != null){
194             lowListTail.next = null;
195         }
196 
197         //:::新扩容elements(index   this.elements.length)插槽 寄存highList
198         newElements[index   this.elements.length] = highListHead;
199         //:::highList末端截断
200         if(highListTail != null){
201             highListTail.next = null;
202         }
203     }
204 
205     /**
206      * 推断是不是须要 扩容
207      * */
208     private boolean needReHash(){
209         return ((this.size / this.elements.length) > this.loadFactor);
210     }
211 
212     //============================================外部接口================================================
213 
214     @Override
215     public V put(K key, V value) {
216         if(needReHash()){
217             reHash();
218         }
219 
220         //:::取得对应的内部数组下标
221         int index = getIndex(key);
222         //:::取得对应桶内的第一个节点
223         EntryNode<K,V> firstEntryNode = this.elements[index];
224 
225         //:::若是以后桶内不存在任何节点
226         if(firstEntryNode == null){
227             //:::建立一个新的节点
228             this.elements[index] = new EntryNode<>(key,value);
229             //:::建立了新节点,size加1
230             this.size  ;
231             return null;
232         }
233 
234         if(firstEntryNode.keyIsEquals(key)){
235             //:::以后第一个节点的key与之婚配
236             V oldValue = firstEntryNode.value;
237             firstEntryNode.value = value;
238             return oldValue;
239         }else{
240             //:::不婚配
241 
242             //:::取得婚配的目的节点的前一个节点
243             EntryNode<K,V> targetPreviousNode = getTargetPreviousEntryNode(firstEntryNode,key);
244             //:::取得婚配的目的节点
245             EntryNode<K,V> targetNode = targetPreviousNode.next;
246             if(targetNode != null){
247                 //:::更新value的值
248                 V oldValue = targetNode.value;
249                 targetNode.value = value;
250                 return oldValue;
251             }else{
252                 //:::在桶链表的末端 新增一个节点
253                 targetPreviousNode.next = new EntryNode<>(key,value);
254                 //:::建立了新节点,size加1
255                 this.size  ;
256                 return null;
257             }
258         }
259     }
260 
261     @Override
262     public V remove(K key) {
263         //:::取得对应的内部数组下标
264         int index = getIndex(key);
265         //:::取得对应桶内的第一个节点
266         EntryNode<K,V> firstEntryNode = this.elements[index];
267 
268         //:::若是以后桶内不存在任何节点
269         if(firstEntryNode == null){
270             return null;
271         }
272 
273         if(firstEntryNode.keyIsEquals(key)){
274             //:::以后第一个节点的key与之婚配
275 
276             //:::将桶链表的第一个节点指向后一个节点(兼容next为null的状况)
277             this.elements[index] = firstEntryNode.next;
278             //:::移除一个节点 size减一
279             this.size--;
280             //:::返回之前的value值
281             return firstEntryNode.value;
282         }else{
283             //:::不婚配
284 
285             //:::取得婚配的目的节点的前一个节点
286             EntryNode<K,V> targetPreviousNode = getTargetPreviousEntryNode(firstEntryNode,key);
287             //:::取得婚配的目的节点
288             EntryNode<K,V> targetNode = targetPreviousNode.next;
289 
290             if(targetNode != null){
291                 //:::将"前一个节点的next" 指向 "目的节点的next" ---> 相当于将目的节点从桶链表移除
292                 targetPreviousNode.next = targetNode.next;
293                 //:::移除一个节点 size减一
294                 this.size--;
295                 return targetNode.value;
296             }else{
297                 //:::若是目的节点为空,申明key其实不存在于哈希表中
298                 return null;
299             }
300         }
301     }
302 
303     @Override
304     public V get(K key) {
305         //:::取得对应的内部数组下标
306         int index = getIndex(key);
307         //:::取得对应桶内的第一个节点
308         EntryNode<K,V> firstEntryNode = this.elements[index];
309 
310         //:::若是以后桶内不存在任何节点
311         if(firstEntryNode == null){
312             return null;
313         }
314 
315         if(firstEntryNode.keyIsEquals(key)){
316             //:::以后第一个节点的key与之婚配
317             return firstEntryNode.value;
318         }else{
319             //:::取得婚配的目的节点的前一个节点
320             EntryNode<K,V> targetPreviousNode = getTargetPreviousEntryNode(firstEntryNode,key);
321             //:::取得婚配的目的节点
322             EntryNode<K,V> targetNode = targetPreviousNode.next;
323 
324             if(targetNode != null){
325                 return targetNode.value;
326             }else{
327                 //:::若是目的节点为空,申明key其实不存在于哈希表中
328                 return null;
329             }
330         }
331     }
332 
333     @Override
334     public boolean containsKey(K key) {
335         V value = get(key);
336         return (value != null);
337     }
338 
339     @Override
340     public boolean containsValue(V value) {
341         //:::遍历悉数桶链表
342         for (EntryNode<K, V> element : this.elements) {
343             //:::取得以后桶链表第一个节点
344             EntryNode<K, V> entryNode = element;
345 
346             //:::遍历以后桶链表
347             while (entryNode != null) {
348                 //:::若是value婚配
349                 if (entryNode.value.equals(value)) {
350                     //:::返回true
351                     return true;
352                 } else {
353                     //:::不婚配,指向下一个节点
354                     entryNode = entryNode.next;
355                 }
356             }
357         }
358 
359         //:::一切的节点都遍历了,没有婚配的value
360         return false;
361     }
362 
363     @Override
364     public int size() {
365         return this.size;
366     }
367 
368     @Override
369     public boolean isEmpty() {
370         return (this.size == 0);
371     }
372 
373     @Override
374     public void clear() {
375         //:::遍历内部数组,将一切桶链表悉数清空
376         for(int i=0; i<this.elements.length; i  ){
377             this.elements[i] = null;
378         }
379 
380         //:::size设置为0
381         this.size = 0;
382     }
383 
384     @Override
385     public Iterator<EntryNode<K,V>> iterator() {
386         return new Itr();
387     }
388 
389     @Override
390     public String toString() {
391         Iterator<EntryNode<K,V>> iterator = this.iterator();
392 
393         //:::空容器
394         if(!iterator.hasNext()){
395             return "[]";
396         }
397 
398         //:::容器肇端运用"["
399         StringBuilder s = new StringBuilder("[");
400 
401         //:::重复迭代
402         while(true){
403             //:::取得迭代的以后元素
404             EntryNode<K,V> data = iterator.next();
405 
406             //:::推断以后元素是不是是末了一个元素
407             if(!iterator.hasNext()){
408                 //:::是末了一个元素,用"]"扫尾
409                 s.append(data).append("]");
410                 //:::返回 拼接终了的字符串
411                 return s.toString();
412             }else{
413                 //:::不是末了一个元素
414                 //:::运用", "支解,拼接到背面
415                 s.append(data).append(", ");
416             }
417         }
418     }
419 
420     /**
421      * 哈希表 迭代器完成
422      */
423     private class Itr implements Iterator<EntryNode<K,V>> {
424         /**
425          * 迭代器 以后节点
426          * */
427         private EntryNode<K,V> currentNode;
428 
429         /**
430          * 迭代器 下一个节点
431          * */
432         private EntryNode<K,V> nextNode;
433 
434         /**
435          * 迭代器 以后内部数组的下标
436          * */
437         private int currentIndex;
438 
439         /**
440          * 默许组织要领
441          * */
442         private Itr(){
443             //:::若是以后哈希表为空,直接返回
444             if(HashMap.this.isEmpty()){
445                 return;
446             }
447             //:::在组织要领中,将迭代器下标移动到第一个有用的节点上
448 
449             //:::遍历内部数组,找到第一个不为空的数组插槽slot
450             for(int i=0; i<HashMap.this.elements.length; i  ){
451                 //:::设置以后index
452                 this.currentIndex = i;
453 
454                 EntryNode<K,V> firstEntryNode = HashMap.this.elements[i];
455                 //:::找到了第一个不为空的插槽slot
456                 if(firstEntryNode != null){
457                     //:::nextNode = 以后插槽第一个节点
458                     this.nextNode = firstEntryNode;
459 
460                     //:::组织要领马上完毕
461                     return;
462                 }
463             }
464         }
465 
466         @Override
467         public boolean hasNext() {
468             return (this.nextNode != null);
469         }
470 
471         @Override
472         public EntryNode<K,V> next() {
473             this.currentNode = this.nextNode;
474             //:::暂存须要返回的节点
475             EntryNode<K,V> needReturn = this.nextNode;
476 
477             //:::nextNode指向本身的next
478             this.nextNode = this.nextNode.next;
479             //:::推断以后nextNode是不是为null
480             if(this.nextNode == null){
481                 //:::申明以后地点的桶链表已遍历终了
482 
483                 //:::寻觅下一个非空的插槽
484                 for(int i=this.currentIndex 1; i<HashMap.this.elements.length; i  ){
485                     //:::设置以后index
486                     this.currentIndex = i;
487 
488                     EntryNode<K,V> firstEntryNode = HashMap.this.elements[i];
489                     //:::找到了后续不为空的插槽slot
490                     if(firstEntryNode != null){
491                         //:::nextNode = 以后插槽第一个节点
492                         this.nextNode = firstEntryNode;
493                         //:::跳出轮回
494                         break;
495                     }
496                 }
497             }
498             return needReturn;
499         }
500 
501         @Override
502         public void remove() {
503             if(this.currentNode == null){
504                 throw new IteratorStateErrorException("迭代器状况非常: 可以或许在一次迭代中举行了屡次remove操纵");
505             }
506 
507             //:::取得须要被移除的节点的key
508             K currentKey = this.currentNode.key;
509             //:::将其从哈希表中移除
510             HashMap.this.remove(currentKey);
511 
512             //:::currentNode设置为null,防备重复挪用remove要领
513             this.currentNode = null;
514         }
515     }
516 }
View Code

哈希表简朴的测试代码:

 1 public class MapTest {
 2     public static void main(String[] args){
 3         testJDKHashMap();
 4 
 5         System.out.println("=================================================");
 6 
 7         testMyHashMap();
 8     }
 9 
10     private static void testJDKHashMap(){
11         java.util.Map<Integer,String> map1 = new java.util.HashMap<>(1,2);
12         System.out.println(map1.put(1,"aaa"));
13         System.out.println(map1.put(2,"bbb"));
14         System.out.println(map1.put(3,"ccc"));
15         System.out.println(map1.put(1,"aaa"));
16         System.out.println(map1.put(2,"bbb"));
17         System.out.println(map1.put(3,"ccc"));
18         System.out.println(map1.put(1,"111"));
19         System.out.println(map1.put(3,"aaa"));
20         System.out.println(map1.put(4,"ddd"));
21         System.out.println(map1.put(5,"eee"));
22         System.out.println(map1.put(6,"fff"));
23         System.out.println(map1.put(8,"ggg"));
24         System.out.println(map1.put(11,"bbb"));
25         System.out.println(map1.put(22,"ccc"));
26         System.out.println(map1.put(33,"111"));
27         System.out.println(map1.put(9,"111"));
28         System.out.println(map1.put(10,"111"));
29         System.out.println(map1.put(12,"111"));
30         System.out.println(map1.put(13,"111"));
31         System.out.println(map1.put(14,"111"));
32 
33         System.out.println(map1.toString());
34         System.out.println(map1.containsKey(1));
35         System.out.println(map1.containsKey(11));
36         System.out.println(map1.containsValue("bbb"));
37         System.out.println(map1.containsValue("aaa"));
38         System.out.println(map1.size());
39         System.out.println(map1.get(1));
40         System.out.println(map1.get(2));
41         System.out.println(map1.get(3));
42         System.out.println(map1.remove(1));
43         System.out.println(map1.remove(2));
44         System.out.println(map1.size());
45 
46     }
47 
48     private static void testMyHashMap(){
49         com.xiongyx.datastructures.map.Map<Integer,String> map2 = new com.xiongyx.datastructures.map.HashMap<>(1,2);
50         System.out.println(map2.put(1,"aaa"));
51         System.out.println(map2.put(2,"bbb"));
52         System.out.println(map2.put(3,"ccc"));
53         System.out.println(map2.put(1,"aaa"));
54         System.out.println(map2.put(2,"bbb"));
55         System.out.println(map2.put(3,"ccc"));
56         System.out.println(map2.put(1,"111"));
57         System.out.println(map2.put(3,"aaa"));
58         System.out.println(map2.put(4,"ddd"));
59         System.out.println(map2.put(5,"eee"));
60         System.out.println(map2.put(6,"fff"));
61         System.out.println(map2.put(8,"ggg"));
62         System.out.println(map2.put(11,"bbb"));
63         System.out.println(map2.put(22,"ccc"));
64         System.out.println(map2.put(33,"111"));
65         System.out.println(map2.put(9,"111"));
66         System.out.println(map2.put(10,"111"));
67         System.out.println(map2.put(12,"111"));
68         System.out.println(map2.put(13,"111"));
69         System.out.println(map2.put(14,"111"));
70 
71         System.out.println(map2.toString());
72         System.out.println(map2.containsKey(1));
73         System.out.println(map2.containsKey(11));
74         System.out.println(map2.containsValue("bbb"));
75         System.out.println(map2.containsValue("aaa"));
76         System.out.println(map2.size());
77         System.out.println(map2.get(1));
78         System.out.println(map2.get(2));
79         System.out.println(map2.get(3));
80         System.out.println(map2.remove(1));
81         System.out.println(map2.remove(2));
82         System.out.println(map2.size());
83     }
84 }
View Code

  我们的哈希表完成是demo级别的,功用简朴,也对照好明白,愿望这可以或许成为人人明白越发庞杂的产等级哈希表完成的一个跳板。在明白了demo级别代码的基础之上,去浏览越发庞杂的产等级完成代码,更好的明白哈希表,更好的明白本身所运用的数据组织,写出更高效,易保护的顺序。

  本系列博客的代码在我的 github上:https://github.com/1399852153/DataStructures ,存在很多不足之处,请多多指教。

-玖富娱乐是一家为代理招商,直属主管信息发布为主的资讯网站,同时也兼顾玖富娱乐代理注册登录地址。