HashMap原理以及面试相关

梦里梦外; 2022-05-17 13:14 211阅读 0赞

# 一、什么是哈希表？ #

hashmap内部维护这一个散列Entry数组和一个线性链表，通过key的hashcode来存储和查找数据。而计算key的hashcode的函数称为**哈希函数**。其新增、查找的操作如下：

![这里写图片描述][70]  
存储结构如下：  
![这里写图片描述][70 1]  
通过哈希函数计算出实际存储地址，在bucket中找到对应的位置进行的查询、新增操作。

## 二、HashMap常见面试问题 ##

1.HashMap的工作原理  
2.HashMap的键和值可以为Null吗？为什么？  
3.如果两个对象的hashcode相同会发生什么？  
4.如何获取hashcode相同的值对象？  
5.如果HashMap大小超过负载因子（load factor：default 0.75）定义的容量，怎么办？  
6.如果要调整HashMap的大小，会存在什么问题？  
7.哪些数据类型适合作为HashMap的键，为什么？  
8.可以用CocurentHashMap替代HashMap吗？

## 三、原理解析 ##

1.HashMap工作原理

> HashMap基于hashing原理，通过put()和get()方法存储和获取对象，当我们调用put函数存储键值对时，会先调用对象的hashCode()方法计算出key的hashcode，然后根据这个值找到bucket的位置来存储值对象。当调用get()方法获取对象的时候，也是先根据key来计算hashcode，然后找到bucket的位置来查找对应的值对象。

2.对于第二个面试题，先来看HashMap的put方法：

//put
    public V put(K key, V value){
     //如果key为null，调用putForNullKey()方法写入null键的值
     //这就是为什么HashMap允许键为null的原因
     if (key == null){
        return putForNullKey(value);
    }
     //根据key的hashCode计算Hash值 
    int hash = hash(key.hashCode());
    //查找hash值在table中的索引
    int i = indexFor(hash, table.length);
    // 如果 i 索引处的 Entry 不为 null，通过循环不断遍历链表查找是否在链表中有相同key的Entry
    //这就是HashMap处理hash碰撞的方法，用一个链表来解决
    for (Entry<K,V> e = tablei; e != null; e = e.next) {
        Object k;
        //找到与插入的值的key和hash相同的Entry
        if (e.hash == hash && ((k = e.key) == key|| key.equals(k)){ 
            //key值相同时直接替换value值，跳出函数
        V oldValue = e.value;
          e.value = value;     e.recordAccess(this);   return oldValue;         }     }
    // 如果 i 索引处的 Entry 为 null 或者key的hash值相同而key不同 ，则需要新增Entry
    modCount++; 
    // 将 key、value 添加到 i 索引处
    addEntry(hash, key, value, i); 
    return null; 
    } 
    //get
    public V get(Object key) 
    { 
    // 如果key是null调用 getForNullKey取出null的value 
    if (key == null) 
    return getForNullKey(); 
    // 根据该key的hashCode值计算它的hash码 
    int hash = hash(key.hashCode()); 
    // 直接取出table数组中指定索引处的值， 
    for (Entry<K,V> e = table[indexFor(hash, table.length)]; 
    e != null; 
    // 搜索该Entry链的下一个对象 
    e = e.next) 
    { 
    Object k; 
    // 如果该Entry的key和hash与被搜索key相同 
    if (e.hash == hash && ((k = e.key) == key 
    || key.equals(k))) 
    return e.value; 
    } 
    return null; 
    }

3.如果两个对象的hashCode相同

> 存储时：它们会找到相同的bucket位置，发生hash碰撞，对每个bucket位置，会有一个维护链表，通过一个next指针指向下一个Entry节点，然后将值存储在这个链表中的next节点。  
> 获取时，会用hashCode找到这个bucket位置，然后遍历这个链表，调用key.equal()方法，找到链表中正确的节点，然后返回要找的键值对对象。

4.HashMap扩容

> HashMap的默认负载因子为0.75，这个负载因子就是用来计算当前的HashMap的容量，当map被填满了75%bucket的时候，将会调用resize()方法，创建原来HashMap两倍大小的bucket数组，并将原来的对象放入新的数组中，这个过程叫rehashing。

5.HashMap键的选择

> 建议使用String、Integer作为键，因为我们可以使用final修饰作为不可变对象，能够很好的防止hashCode重复导致发生hash碰撞，这样可以提高HashMap的性能，因为不用去遍历链表去查找元素。

6.ConcurrentHashMap

> ConcurrentHashMap可以替换HashMap。要根据使用场景来选择，如果考虑多线程的问题，使用ConcurrentHashMap比较好，因为它仅仅根据同步级别对map的一部分进行上锁，效率要高一些。但是在不考虑多线程的应用场景中，HashMap会更好。

## 四、总结以及其他注意点 ##

*  **选用String、Integer作为键会提高HashMap的效率。**
 *  **如果HashMap的大小超过负载因子定义的容量，会创建一个原来两倍大小的新bucket数组，将原来的对象放入新数组，这个过程影响效率且容易引发线程不安全问题，因为多个线程同时发现需要调整容量时，会出现条件竞争的现象，因为可能形成一个环形的链表，导致所有的next指向都不为null，进入死循环。**
 *  **多线程同时进行put操作也可能导致数据丢失。**

参考： —— [ \[ HashMap实现原理及源码分析 \]][_ HashMap_]

[70]: /images/20220517/28613da0d18d47a6a4b596e99bc38b4f.png
[70 1]: /images/20220517/7cc495188b5b4a2299d017fc53229a6a.png
[_ HashMap_]: https://www.cnblogs.com/chengxiao/p/6059914.html