『哈希表』 究竟是怎么回事

一开始我们先了解几种常用的数据结构

数组 :采用一段连续的存储单元来存储数据。对于指定下标的查找,时间复杂度为O(1);通过给定值进行查找,需要遍历数组,逐一比对给定关键字和数组元素,时间复杂度为O(n),

线性链表 :对于链表的新增,删除等操作(在找到指定操作位置后),仅需处理结点间的引用即可,时间复杂度为O(1),而查找操作需要遍历链表逐一进行比对,复杂度为O(n)

哈希表 :相比上述几种数据结构,在哈希表中进行添加,删除,查找等操作,性能十分之高,不考虑哈希冲突的情况下(后面会探讨下哈希冲突的情况),仅需一次定位即可完成,时间复杂度为O(1),接下来我们就来看看哈希表是如何实现达到惊艳的常数阶O(1)的。

我们知道,数据结构的物理存储结构只有两种: 顺序存储结构链式存储结构 (像栈,队列,树,图等是从逻辑结构去抽象的,映射到内存中,也这两种物理组织形式),而在上面我们提到过,在数组中根据下标查找某个元素,一次定位就可以达到,哈希表利用了这种特性, 哈希表的主干就是数组

比如我们要新增或查找某个元素,我们通过把当前元素的关键字 通过某个函数映射到数组中的某个位置,通过数组下标一次定位就可完成操作。

HashMap

HashMap是java.util包中的一个集合框架类,它是java.util.Map的实现类,具有方便、高效的基于键值对存取的功能,其平均查询时间复杂度为O(1),非线性安全。

HashMap是一种用 哈希表 + 链表 + 红黑树 等数据结构实现的基于key-value存取的工具类,在JDK1.8之前没有红黑树这一数据结构,在JDK1.8之后对其进行了优化:考虑到发生大量Hash碰撞时链表查询效率低,所以加入了红黑树这一数据结构以提高此种情况的查询效率,通过阈值控制,将链表和红黑树进行相互转化

HashMap的工作原理

H ashMap基于hashing原理,我们通过 put()get() 方法储存和获取对象。当我们将键值对传递给put()方法时,它调用键对象的hashCode()方法来计算hashcode,让后找到bucket位置来储存值对象。

当获取对象时,通过键对象的equals()方法找到正确的键值对,然后返回值对象。HashMap使用链表来解决碰撞问题,当发生碰撞了,对象将会储存在链表的下一个节点中。

HashMap在每个链表节点中储存键值对对象。在jdk1.8中, 如果链表的长度超过了阈值,链表就会转换成红黑树 ,来提高性能,当红黑树的节点个数小于6的时候,又会转化成链表。

    

如果所有的桶都满了( 容量 * 负载因子(0.75) ),这个时候就需要扩容 resize(),并且重新计算Node对象的位置重新排列。

HashMap源码解读

类定义

HashMap是Map类的实现类,同时继承了AbstractMap类、实现了Cloneable类、Serializable类,后面两个标志性的接口赋予了它可克隆、可序列化的能力。

//  HashMap类,继承自AbstractMap,实现了Map接口
//  并且实现了两个标志性接口,赋予了它可克隆、可序列化的能力
public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
}

常量定义

//  序列化ID,作为唯一识别标志,用于序列化和反序列化
private static final long serialVersionUID = 362498820763181265L;

//  默认初始化容量大小,为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

//  最大容量:2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;

//  负载因子,在扩容时使用
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//  一个桶的树化阈值
//  当桶中元素个数超过这个值时,需要使用红黑树节点替换链表节点
static final int TREEIFY_THRESHOLD = 8;

//  一个树的链表还原阈值
//  当扩容时,桶中元素个数小于这个值,就会把树形的桶元素 还原(切分)为链表结构
static final int UNTREEIFY_THRESHOLD = 6;

//  哈希表的最小树形化容量
//  当哈希表中的容量大于这个值时,表中的桶才能进行树形化
//  否则桶内元素太多时会扩容,而不是树形化
//  为了避免进行扩容、树形化选择的冲突,
//  这个值不能小于 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;

常规方法

//  经常使用的,获取hash表中已经存在的键值对数量
//  注意这里的size并非是hash表的大小,而是实际存在的键值对数量
public int size() {
    return size;
}

//  是否为空,即是否实际存在键值对(与table容量无关)
public boolean isEmpty() {
    return size == 0;
}
//  检测是否存在key
//  逻辑和get类似,主要是调用getNode方法
public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}
//  检测是否存在value
public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    //遍历哈希桶上的每一个链表
    if ((tab = table) != null && size > 0) {
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                //如果找到value一致的返回true
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}
//  批量存入一个Map,逻辑和构造函数中相同,主要调用putMapEntries
public void putAll(Map<? extends K, ? extends V> m) {
    putMapEntries(m, true);
}

查询方法(get)

根据key查询,找到返回value,没找到返回null,逻辑如下:

//  根据key获取值
public V get(Object key) {
    Node<K,V> e;
    //  根据key的值和扰动后key的hash值先得到Node节点,然后获取其中的值
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

//  JDK8新增的方法,查询到则返回其value,没有则返回设定的缺省值
public V getOrDefault(Object key, V defaultValue) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
}

//  根据扰动后的hash值和key的值获取节点
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //  基本逻辑:先找到相应节点,然后返回,如果不存在返回null

    //  table不为空并且其大小大于0才继续
    if ((tab = table) != null && (n = tab.length) > 0 &&
        //  hash和n-1进行区域后定位到桶的位置,然后获取其头结点first
        (first = tab[(n - 1) & hash]) != null) {
        //  如果头结点恰好是该节点则直接返回
        //  检测内容:头节点的hash是否相同,key是否相同(检测内存地址或检测值)
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        //  头结点不是要找的节点,接下来取得下一个节点进行寻找
        if ((e = first.next) != null) {
            //  如果桶内的数据结构是红黑树,那么就调用getTreeNode方法去查找
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            //  如果不是红黑树,即是连表,则循环遍历,直到查找到该节点
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

插入/更新方法(put)

向表中插入或更新一个值

//  插入新的值,主要调用putVal方法,详细逻辑见putVal()
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

//  插入新值核心函数
//  如果参数onlyIfAbsent是true,那么不会覆盖相同key的值value
//  如果evict是false,表示是在初始化时调用的
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //  首先检查table是否是null并且容量是否大于0,即有没有初始化table
    //  如果没有初始化就进行resize扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //  先定位到桶的位置,p为该桶的头节点
    //  如果p为null则说明该桶还没有节点,直接将新键值对存入桶中
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    //  桶内头节点p不为空,即发生了hash碰撞,进一步处理
    else {
        Node<K,V> e; K k;
        //  比较头节点的扰动hash值及key值
        //  如果相同则说明存入的节点key已存在,而且就是头节点
        //  先获取该节点,是否覆盖其值进一步处理
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //  头节点的key和插入的key不相同
        //  先判断桶内数据结构是否是红黑树,如果是则以红黑树的方式插入到树中
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //  桶内节点不是红黑树,即链表结构
        else {
            //  循环遍历该链表
            //  直到找到与插入节点key相同的节点,没找到就直接插入到尾结点
            for (int binCount = 0; ; ++binCount) {
                //  已经遍历到了尾节点,说明插入的key不存在,直接插入到尾部
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //  如果桶内节点数量达到了树型化阈值,则进行树型化
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //  插入的key已经存在,先获取该节点,是否覆盖其值进一步处理
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //  如果获取到的节点不为null则进行操作
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            //  方法传入的onlyIfAbsent参数为false,或者旧值为null则直接替换掉旧值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            //  这是一个空实现的函数,用作LinkedHashMap重写使用
            afterNodeAccess(e);
            return oldValue;
        }
    }

    //  以上操作以及全部完成,并且已经成功插入或更改一个节点的值
    //  修改modCount的值,记录修改次数
    ++modCount;
    //  更新size,并判断如果超过了阈值则进行扩容
    if (++size > threshold)
        resize();
    //  这是一个空实现的函数,用作LinkedHashMap重写使用
    afterNodeInsertion(evict);
    return null;
}

桶的树形化 treeifyBin()

如果一个桶中的元素个数超过 TREEIFY_THRESHOLD(默认是 8 ) ,就使用红黑树来替换链表,提高查询效率

//将桶内所有的链表节点替换成红黑树节点
final void treeifyBin(Node[] tab, int hash) {
    int n, index; Node e;
    //如果当前哈希表为空,或者哈希表中元素的个数小于进行树形化的阈值(默认为 64),就去新建/扩容
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        //如果哈希表中的元素个数超过了树形化阈值,进行树形化
        // e 是哈希表中指定位置桶里的链表节点,从第一个开始
        TreeNode hd = null, tl = null; //红黑树的头、尾节点
        do {
            //新建一个树形节点,内容和当前链表节点 e 一致
            TreeNode p = replacementTreeNode(e, null);
            if (tl == null) //确定树头节点
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        //让桶的第一个元素指向新建的红黑树头结点,以后这个桶里的元素就是红黑树而不是链表了
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

删除节点 remove()

删除操作是根据key先找到对应的Node节点,然后再删除,如果没找到直接返回null,其操作和get()非常相似

//  根据key删除一个节点,其主要是调用removeNode方法
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

//  删除节点的核心方法
//  如果参数matchValue是true,则必须key、value都相等才删除。
//  如果movable参数是false,在删除节点时,不移动其他节点
final Node<K,V> removeNode(int hash, Object key, Object value,
                            boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    //  在删除之前先确认表是否为空,并且其容量大于0
    //  同时根据key定位到桶位置中桶不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        //  如果头结点就是要删除的节点,则直接赋值给node
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        //  如果还存在后续节点就继续寻找要删除的节点
        else if ((e = p.next) != null) {
            //  如果桶内数据结构是红黑树,则在红黑树中找出该节点
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                //  如果是链表,则循环遍历查找
                //  注意此时p是删除节点的前驱节点,node是被删除的节点
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                            (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        //  如果要删除的节点找到了,就进行删除操作,否则返回null
        //  matchValue是true则要求key和value都必须相等
        if (node != null && (!matchValue || (v = node.value) == value ||
                                (value != null && value.equals(v)))) {
            //  根据不同的数据结构进行删除相应的节点
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;//  记录修改数
            --size;//  键值对数量-1
            afterNodeRemoval(node);//  这是一个空实现的函数,LinkedHashMap回调函数
            return node;
        }
    }
    return null;
}

扩容 resize()

resize是 非常重要 的一个函数,它负责了HashMap中动态扩容的核心逻辑,其主要逻辑如下:

  1. 备份旧表、旧表容量、旧表阈值,定义新表的容量、阈值

  2. 如果旧表容量大于0

  • 如果旧表容量已经达到上限,则设置阈值为最大整数,不再进行扩容

  • 如果旧表容量未达上限,设置新表容量为旧表容量的2倍,但前提是新表容量也得在上限范围内

  1. 如果旧表容量为空,但是阈值大于0,说明初始化时指定了容量和阈值,旧表的阈值则作为新表的容量

  2. 如果旧表容量为空,并且阈值为0,说明初始化时没有指定容量和阈值,则将默认的初始容量和阈值作为新表的容量和阈值

  3. 如果以上操作之后新表的阈值为0,根据新表容量和负载因子求出新表的阈值

  4. 创建一个新的表,其数组长度为新表容量

  5. 如果旧表不为空,就进行数据迁移,迁移时依次遍历每个桶

  • 如果桶中只有一个节点,则直接放入新表对应位置的桶中

  • 如果桶中不止一个节点,并且结构是红黑树,则进行拆分红黑树然后迁移

  • 如果桶中不止一个节点,并且结构是链表,则分为高位和低位分别迁移(高位= 低位 + 原哈希桶容量),低位放入新表对应旧表桶索引中,高位放入新表对应新的桶索引中

//  hash扩容核心函数
final Node<K,V>[] resize() {
   //  先存一个旧table
   Node<K,V>[] oldTab = table;
   //  旧table的容量
   int oldCap = (oldTab == null) ? 0 : oldTab.length;
   //  旧table的阈值
   int oldThr = threshold;
   //  定义新table的容量和阈值
   int newCap, newThr = 0;
   //  如果旧table容量大于0
   if (oldCap > 0) {
       //  旧table容量已经达到上限,则设置阈值为最大整数,不再进行扩容
       if (oldCap >= MAXIMUM_CAPACITY) {
           threshold = Integer.MAX_VALUE;
           return oldTab;
       } //  容量未达到上限,新table容量是旧table的2倍(前提是在上限范围内)
       else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                   oldCap >= DEFAULT_INITIAL_CAPACITY)
           newThr = oldThr << 1; // double threshold
   }// 表示空的,但是阈值大于0,说明初始化时指定了容量、阈值
   else if (oldThr > 0) // initial capacity was placed in threshold
       newCap = oldThr;//  则直接把旧阈值作为新table的容量
   else {  // 既没有初始化容量又没有初始化阈值,那么就进行初始化
       newCap = DEFAULT_INITIAL_CAPACITY;
       newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
   }
   if (newThr == 0) {
       float ft = (float)newCap * loadFactor;//根据新table容量和加载因子求出新的阈值
       newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                   (int)ft : Integer.MAX_VALUE);//   进行越界限定
   }
   //  更新阈值
   threshold = newThr;
   //  创建一个新的table
   @SuppressWarnings({"rawtypes","unchecked"})
       Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
   //  把新的table直接赋值给table,原来存放值的table内存是被oldTab变量所指向
   table = newTab;
   //  如果旧table不为空,那么就进行节点迁移
   if (oldTab != null) {
       for (int j = 0; j < oldCap; ++j) {
           Node<K,V> e;
           //  依次获取旧table中桶中的首节点
           if ((e = oldTab[j]) != null) {
               oldTab[j] = null;// 清理旧表中该桶的内存空间,防止内存泄漏
               if (e.next == null)//   如果桶中只有一个节点,直接存入新table中
                   newTab[e.hash & (newCap - 1)] = e;
               else if (e instanceof TreeNode)//   桶中不止一个节点,并且结构是红黑树,则进行拆分
                   ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
               else { // preserve order
                   //  因为扩容是容量翻倍,所以原链表上的每个节点
                   //  现在可能存放在原来的下标,即低位,
                   //  或者扩容后的下标,即高位。
                   //  高位=  低位 + 原哈希桶容量
                   //  低位链表的头结点、尾节点
                   Node<K,V> loHead = null, loTail = null;
                   //  高位链表的头结点、尾节点
                   Node<K,V> hiHead = null, hiTail = null;
                   Node<K,V> next;
                   do {
                       next = e.next;
                           // 利用哈希值和旧的容量取与,可以得到哈希值去模后,是大于等于oldCap还是小于oldCap
                           // 等于0代表小于oldCap,应该存放在低位,否则存放在高位
                       if ((e.hash & oldCap) == 0) {
                           if (loTail == null)
                               loHead = e;
                           else
                               loTail.next = e;
                           loTail = e;
                       }// 高位则处理和低位相反
                       else {
                           if (hiTail == null)
                               hiHead = e;
                           else
                               hiTail.next = e;
                           hiTail = e;
                       }
                   } while ((e = next) != null);
                   //  低位链表存放在原来的桶索引中
                   if (loTail != null) {
                       loTail.next = null;
                       newTab[j] = loHead;
                   }
                   //  高位链表存放在新的桶索引中
                   if (hiTail != null) {
                       hiTail.next = null;
                       newTab[j + oldCap] = hiHead;
                   }
               }
           }
       }
   }
   return newTab;
}

为了更好理解代码的调用,下图列出一些方法之间的调用关系:

HashMap常见面试题

HashMap的数组长度为什么一定要是2的幂

答:hashMap的数组长度一定保持2的次幂,数组长度保持2的次幂,length-1的低位都为1,会使得获得的数组索引index分布更加均匀

如果不是2的次幂,也就是低位不是全为1此时,低位有可能是0,计算hash值得时候冲突几率变大,发生hash碰撞,会造成空间的。

为什么String, Interger这样的wrapper类适合作为键

String, Interger这样的wrapper类作为HashMap的键是再适合不过了,而且String最为常用。因为String是不可变的,也是final的,而且已经重写了equals()和hashCode()方法了。

其他的wrapper类也有这个特点。不可变性是必要的,因为为了要计算hashCode(),就要防止键值改变,如果键值在放入时和获取时返回不同的hashcode的话,那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。

如果你可以仅仅通过将某个field声明成final就能保证hashCode是不变的,那么请这么做吧。因为获取对象的时候要用到equals()和hashCode()方法,那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话,那么碰撞的几率就会小些,这样就能提高HashMap的性能。

当两个对象的hashcode相同会发生什么

当两个对象的hashcode相同的时候,所以它们的bucket位置相同,会发生碰撞,因为hashmap使用链表来存储key ,value的键值对,所以这个Entry (包含有键值对的Map.Entry对象)会存储在链表中。

如果两个键的hashcode相同,你如何获取值对象

当我们调用 get() 方法的时候,HashMap会先调用hash算法算出当前key的hash值 , 和当前table 的长度 -1 进行运算 ,算出它们的 bucket 位置,因为HashMap中的 Entry 存储的是 key ,value 键值对 , 调用 key.equals 方法拿到正确的Entry对象 ,返回Entry的value。

如果HashMap的大小超过了负载因子(load factor)定义的容量,怎么办

默认的负载因子大小为0.75,也就是说,当一个map填满75%的时候,和其他集合类一样,将会创建原来HashMap大小的两倍的数组,来重新调整map的大小,并将原来的对象放入新的数组,这个过程叫做rehashing,因为它调用hash方法找到新的位置。这个值只可能在两个地方,一个是原下标的位置,另一种是在下标为<原下标+原容量>的位置。

有什么方法可以减少hash碰撞

  • 扰动函数可以减少碰撞,原理是他让内容不同的对象返回不同的hashcode值,这样就会少产生碰撞,也就是在数据结构中链表的结构少了,在取值时,会很少的调用equals方法,提高Map的性能,扰动hash方法的内部算法实现,目的是让不同的对象返回不同的hashcode。

  • 使用不可变的,声明为final的对象做键值,如String Integer。不可变使得能够缓存不同键的hashcode。这将提高整个回去对象的速度。

  • 因为String是final的,而且已经重写了equals()和hashCode()方法了。不可变性是必要的,因为为了要计算hashCode(),就要防止键值改变,如果键值在放入时和获取时返回不同的hashcode的话,那么就不能从HashMap中找到你想要的对象。

HashMap中的hash函数怎么实现的

return (n-1)&(h^(h>>>16));n是数组的初始化长度,h是hashcode返回的散列值也就是key的hash值。
简单来说就是:

  • 高16bit不变,低16bit和高16bit做了一个异或运算

  • n-1&hash 得到下标。

拉链法导致的链表过深问题为什么不用二叉树代替,而选择红黑树?为什么不一直使用红黑树

之所以选择红黑树,是因为二叉树在特定情况下,会形成一条线的结构,这跟链表查询的一样了,造成查询很深的问题,遍历查询会变的非常的慢,

二红黑树就是为了查询速度快,解决链表查询深度的问题,我们知道红黑树是属于平衡二叉树,但是为了保持平衡是需要付出代价的,但是该代价所损耗的资源要比遍历线性链表要少,所以当长度大于8的时候,会使用红黑树,如果链表的长度很短 的话,使用红黑树,反而会更慢。

扫码关注我,加入 每日一题算法交流群/秋招备战群

请备注  学校+昵称   才可以加群噢

我来评几句
登录后评论

已发表评论数()

相关站点

热门文章