阿里面试90%以上会问到的数据结构；HashMap

电玩女神 2022-02-13 02:09 99阅读 0赞

# **BAT面试必问；** #

**关于hashmap，你知道多少？你知道hashmap的工作原理吗？**

1.该问题很有深度

2.能答出多少决定岗位和薪资.

3.问题的方式多种多样

# **一.首先我们了解下HashMap是什么** #

HashMap是Java常用的用来储存键值对的数据结构，它是线程不安全的，可以储存null键值，这些大家经常用，也都知道，接下来根据源码分析一下HashMap的实现。

**1、实现原理**

HashMap采用数组散列+链表的方式来储存键值对，键值对的对象实现如下：

static class Entry<K,V> implements Map.Entry<K,V> { 
     final K key; 
     V value; 
     Entry<K,V> next; 
     final int hash; 
     …… 
    }

通过一个Entry的数组table就实现了多个对象的保存，使用哈希值和键值解决了在插入和查找时的冲突。

**2、put方法，写入键值对**

public V put(K key, V value){
     //如果 key 为 null，调用 putForNullKey 方法写入null键的值
     if (key == null){
     return putForNullKey(value);
    }
    //根据 key 的 keyCode 计算 Hash 值 
    int hash = hash(key.hashCode());
    //查找hash值在table中的索引
    int i = indexFor(hash, table.length);
    // 如果 i 索引处的 Entry 不为 null，通过循环不断遍历链表查找是否在链表中有相同key的Entry
    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; 
    }

在put方法中解决hash碰撞的方式很清楚，即当两个entry的hash值相同时，需要对key值是否相同进行判断，只有key和hash都相同，才能进行修改，否则认为不是同一个entry。

**3.addEntry的实现**

代码：

void addEntry(int hash, K key, V value, int bucketIndex) { // 获取指定 bucketIndex 索引处的 Entry
    Entry<K,V> e = tablebucketIndex; 
    tablebucketIndex = new Entry<K,V>(hash, key, value, e); // 如果 Map 中的 key-value 对的数量超过了极限
    if (size++ >= threshold)
     resize(2 table.length);
    }

在创建新Entry时如果table的bucketIndex处有元素的话，创建时需要将entry的next设置为原先存储的元素。

# 二，HashMap工作原理 #

**以下为目录，有需要完整进阶视频可以加Android进阶群；701740775免费获取**

**1.目录**

![webp][]

**2.顺序表与链表**

![webp 1][]

**3.Hsh表**

![webp 2][]

![webp 3][]

![webp 4][]

**4.Hash源码**

![webp 5][]

**5.碰撞**

![webp 6][]

### **需要完整进阶视频详解可以加Android进阶群；701740775免费获取！** ###

### 附录Android高级技术大纲和进阶视频； ###

![webp 7][]

[webp]: /images/20220213/85585a9928134d9da67f3ef9edd85e88.png
[webp 1]: /images/20220213/78f2c9008cbd45f7aae9c44b1ab14e15.png
[webp 2]: /images/20220213/37a2edbcc78d4b36aebe47efd760d91e.png
[webp 3]: /images/20220213/40baaaf5b9ee4489aec895b68fca99eb.png
[webp 4]: /images/20220213/8a363a974c1f4a4c89abc5f39dd7fe4a.png
[webp 5]: /images/20220213/10183fafc85a4962a9a450e835181912.png
[webp 6]: /images/20220213/b62464ffe29546a8be64f7db33014750.png
[webp 7]: /images/20220213/9d2271294e4c4742b193a6990f517798.png