手写HashMap（基于JDK1.7）

墨蓝 2024-04-06 14:05 73阅读 0赞

### 1、HashMap结构： ###

**Java7 : 数组 + 链表**  
![在这里插入图片描述][d825c1437b7844fe89054602ba2a83c9.png]

Java8 : 数组 + 链表 或 红黑树 (链表超过8则转为红黑树，小于6则变会链表) >> 加快查询  
![在这里插入图片描述][65895320ef9d4f5d9df168439678c104.png]  
JDK1.7和JDK1.8的区别是基于数组上的链表是否转换成红黑树，本篇文章着重讲JDK1.7的HashMap实现。

### 2、存取操作： ###

#### 1）存储元素过程： ####

写操作就是在散列表中插入新的键值对（在JDK中叫作**Entry**或**Node**）  
在Entry中保存key和值，以及next指针

Entry{
        
    	int key; 
    	Object value; 
    	Entry next; 
    }

**第1步，通过哈希函数，把Key转化成数组下标**

//数组下标=取key的hashcode模数组的长度后的余数 
    index = HashCode (Key) % Array.length;
    int index=Math.abs("Hello".hashCode())%10; //（0-9）

**第2步，如果数组下标对应的位置没有元素，就把这个Entry填充到数组下标的位置。**  
假设key的hashcode为13，数组长度为 8，则要存储在数组索引为5的位置（13  
% 8=5）  
![在这里插入图片描述][558cfc99f8c04c048bcd6336e508f046.png]  
**Hash冲突（碰撞）**  
由于数组的长度是有限的，当插入的Entry越来越多时，不同的Key通过哈希函数获得的下标有可能是相同的，这种情况，就叫作**哈希冲突**。  
![在这里插入图片描述][3f10d5fbf1284466b0224d679f3d8d74.png]

**链表法**：数组的每一个元素不仅是一个Entry对象，还是一个链表的头节点。每一个Entry对象通过next指针  
指向它的下一个Entry节点。当新来的Entry映射到与之冲突的数组位置时，只需要插入到对应的链  
表中即可，默认next指向null![在这里插入图片描述][6509734bb51a43c5b2c13b0286aa7039.png]

#### 2）读取元素过程： ####

读操作就是通过给定的Key，在hash表中查找对应的Value  
**第1步，通过哈希函数，把Key转化成数组下标**。  
**第2步，找到数组下标所对应的元素，如果key不正确，说明产生了hash冲突，**  
则顺着头节点遍历该单链表，再根据key即可取值  
![在这里插入图片描述][54f3cf5480524d7ebcf666cc82c48743.png]  
**Hash扩容（resize）**  
Hash表是基于数组实现的，所以散列表需要扩容  
当经过多次元素插入，散列表达到一定饱和度时，Key映射位置发生冲突的概率会逐渐提高。这样  
一来，大量元素拥挤在相同的数组下标位置，形成很长的链表，对后续插入操作和查询操作的性能  
都有很大影响  
影响扩容的因素有两个  
Capacity：HashMap的容量长度  
LoadFactor：HashMap的负载因子（阈值），默认值为0.75f  
当**HashMap.Size >= Capacity×LoadFactor**时，需要进行扩容

扩容的步骤：

1.  扩容，创建一个新的Entry空数组，长度是原数组的2倍
2.  重新Hash，遍历原Entry数组，把所有的Entry重新Hash到新数组中  
    ![在这里插入图片描述][e1f1039293f44935bfb76bc259cb5ab3.png]

### 3、代码实现 ###

##### 1）Node.java #####

public class Node {
        
        String key;
        String value;
    
        // 指向下一个结点
        Node next;
    
        public Node(String key, String value, Node next) {
        
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

说明：作为存储数据的数据结构，类似于上图数组中的Entry

##### 2）ListNode.java #####

/**
     * 单链表
     */
    public class ListNode {
        
    
        Node head; //头结点
    
        /** 添加单链表结点
         * @param key
         * @param value
         */
        public void addNode(String key, String value) {
        
            // 无头结点，在调用处设置，这里直接返回
            if (head == null) return;
    
            /* 以下是有头结点情况 */
            // 创建结点
            Node node = new Node(key, value, null);
    
            // 临时变量
            Node tmp = head;
            // 循环单链表
            while (true) {
        
                //key相同覆盖值 从head开始
                if(key.equals(tmp.key)){
        
                    tmp.value=value;
                }
                // 到达尾结点，跳出循环
                if(tmp.next==null){
        
                    break;
                }
                //指向下一个
                tmp=tmp.next;
            }
    
            //在循环外，将新增的结点挂载在末尾
            tmp.next=node;
        }
    
    
        /**
         * 获得值
         *  @param key
         *  @return
         */
        public String getVal(String key) {
        
            // 如果头结点为空，说明没值
            if (head == null) return null;
    
            //只有一个结点，那么直接返回头节点的值
            if (head.next == null) {
        
                return head.value;
            }
            // 多个节点时，遍历单链表
            else {
        
                // 临时变量
                Node tmp = head;
                while (tmp != null) {
        
                    //找到匹配的key
                    if (key.equals(tmp.key)) {
        
                        return tmp.value;
                    }
                    //指向下一个
                    tmp = tmp.next;
                }
                return null;
            }
        }
    }

说明：以上代码，实现了在链表中添加和查询元素Node，  
添加操作，相当于在链表末尾进行添加

##### 3）MyHashMap.java #####

/***
     * 手动HashMap
     */
    public class MyHashMap {
        
        //数组初始化 2的n次方
        ListNode[] map=new ListNode[8];
    
        //ListNode的个数，数组中每个槽位会对应一个ListNode
        int size;
    
        /**
         * 设置值
         * @param key
         * @param value
         */
        public void put(String key,String value){
        
            //该扩容了
            if(size>=map.length*0.75){
        
                // 扩容操作，略
                System.out.println("map需要扩容");
                return;
            }
    
            //计算索引 数组下标
            int index=Math.abs(key.hashCode())%map.length;
    
            //获得该下标处的ListNode
            ListNode ln=map[index];
            //该下标处无值，将头结点添加进去
            if(ln==null){
        
                //创建单链表
                ListNode lnNew=new ListNode();
                //创建头结点
                Node head=new Node(key,value,null);
                //挂载头结点
                lnNew.head=head;
                //把单链放到数组里
                map[index]=lnNew;
                //占用1个下标，计数加1
                size++;
            }
    
            //该下标有值，hash碰撞
            else {
        
                //单链表挂结点
                ln.addNode(key,value);
            }
        }
    
        /**
         * 取值
         * @param key
         * @return
         */
        public String get(String key){
        
            int index=Math.abs(key.hashCode())%map.length;
            ListNode ln=map[index];
            if(ln==null)
                return null;
            return ln.getVal(key);
        }
    
        //测试
        public static void main(String[] args) {
        
            MyHashMap hashMap=new MyHashMap();
            hashMap.put("m3","cccccc");  //和c1的hash值相同
            hashMap.put("c1","kkkkkk");  //和m3的hash值相同,产生hash碰撞
            hashMap.put("c1","mmmmmmm");  //和上一行key值相同，value进行覆盖
            System.out.println(hashMap.get("c1"));
        }
    
    }

说明：当产生Hash碰撞的时候，就会引用到单链表结构 ListNode了

测试  
![在这里插入图片描述][2c261c75421947f5929ac97994a52946.png]

[d825c1437b7844fe89054602ba2a83c9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/43c7c95a989f46fda4e8050c896a23b6.png
[65895320ef9d4f5d9df168439678c104.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/7806e87a103c4e2bb236b835efaf8c70.png
[558cfc99f8c04c048bcd6336e508f046.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/8019d3de0ba141aab21d2331586a653e.png
[3f10d5fbf1284466b0224d679f3d8d74.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/7e6b544763af40b68429251d61caf6f8.png
[6509734bb51a43c5b2c13b0286aa7039.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/9e3215eae7ad48f48cda3a92b7d0aded.png
[54f3cf5480524d7ebcf666cc82c48743.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/f8fc965f90ed4bfc90485944c7a2163a.png
[e1f1039293f44935bfb76bc259cb5ab3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/8ffa6a31449f49e9a0878cb5bdb559e0.png
[2c261c75421947f5929ac97994a52946.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/f3e69acf33264b498b78614cb3e6e0c0.png