什么是HashMap

红太狼 2023-02-13 14:58 135阅读 0赞

### 什么是HashMap ###

HashMap是一个用于存储Key-Value键值对的集合，每一个键值对也叫做Entry。这些个键值对（Entry）分散存储在一个数组当中，这个数组就是HashMap的主干。HashMap数组每一个元素的初始值都是Null。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDYyNDQxMA_size_16_color_FFFFFF_t_70]  
**核心理论**：基本原理就是把任意长度的输入，通过Hash算法变成固定长度的输出。  
这个映射的规则就是对应的Hash算法，而原始数据映射后的二进制串就是哈希值。

**Hash的特点**：  
1.从hash值不可以反向推导出原始的数据  
2.输入数据的微小变化会得到完全不同的hash值，相同的数据会得到相同的值  
3.哈希算法的执行效率要高效，长的文本也能快速地计算出哈希值  
4.hash算法的冲突概率要小

由于hash的原理是将输入空间的值映射成hash空间内，而hash值的空间远小于输入的空间。根据抽屉原理，一定会存在不同的输入被映射成相同输出的情况。

**抽屉原理**：桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果。这一现象就是我们所说的“抽屉原理”。

对于HashMap，我们最常使用的是两个方法：**Get 和 Put。**

1.  Put方法  
    调用Put方法的时候发生了什么呢？比如调用 hashMap.put(“apple”, 0) ，插入一个Key为“apple"的元素。  
    但是，因为HashMap的长度是有限的，当插入的Entry越来越多时，我们j就可以利用链表来解决。HashMap数组的每一个元素不止是一个Entry对象，也是一个链表的头节点。每一个Entry对象通过Next指针指向它的下一个Entry节点。当新来的Entry映射到冲突的数组位置时，只需要插入到对应的链表即可。
2.  Get方法  
    使用Get方法根据Key来查找Value，由于刚才所说的Hash冲突，同一个位置有可能匹配到多个Entry，这时候就需要顺着对应链表的头节点，一个一个向下来查找。

--------------------

下面我们实现一下存储已存在的值。

/** * 自定义map * 用于存取键值重复数据 * @param <K> * @param <V> */
    private class TempMap<K,V> { 
        private HashMap<K, ArrayList<V>> data = new HashMap<>();
        public boolean add(K k, V v) { 
    　　　　　// 判断是否存在key
            if (data.containsKey(k)) { 
                data.get(k).add(v);
            } else { 
                ArrayList<V> list = new ArrayList<>();
                list.add(v); data.put(k,list);
            }
            return true;
        }
        public HashMap<K,ArrayList<V>> getData() { 
            return data;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDYyNDQxMA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200529220203417.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDYyNDQxMA==,size_16,color_FFFFFF,t_70