JAVA集合——HashMap的简述

首先附上HashMap结构图一张，方便大家更好的认其底层数据结构，本篇博客主要是对HashMap基本知识以及如何实现HashMap的总结。

一、HashMap的底层数据结构

首先介绍我们会涉及到的基础数据结构
1）数组:对于数组而言，可以根据所找值的索引直接查找该值的位置，即查找容易，删除插入不易。
2）链表：对于链表而言，查找不易，删除插入容易。
3）红黑树：：一种自平衡二叉查找树O(log2N) 的时间内做查找、添加、删除。
4）哈希表又称为散列表，是根据关键码key直接访问内存存储位置的数据结构，即通过关于key的函数，映射到一个地址来访问数据，这样来加快查找速度。
HashMap底层则是基于哈希表实现的，但是当同一位置的元素越来越多，hash值相等的元素也越来越多时，使用key查找的效率也会越来越低。
为了解决这种问题即哈希冲突：
jdk1.8之前，引入链表，使用数组加链表的数据结构；jdk1.8之后则采用数组+链表+红黑树，引入红黑树是当链表的阈值超过8并且数组长度大于64时，链表即会转为红黑树，从而减少了查询时间从O(N)->O(log2N)，极大的提高了数据查询性能。

二、HashMap的使用

HashMap简单使用示例：

public class TestDemo2 {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("ywj", 10);
        map.put("zhangsan", 20);
        map.put("hhhh", 30);     //具体实现都在HashMap
        System.out.println(map.isEmpty());
        map.remove("ywj", 10);
        System.out.println(map.size());
        map.containsKey("zhangsan");
        map.containsValue(10);
        //利用迭代器遍历打印出所有元素
        //每一个元素作为一个节点   称为Entry节点   作为set返回
        // 获取所有节点的集合
        Set<Map.Entry<String, Integer>> entries = map.entrySet();
        //获取set集合的迭代器对象
        Iterator<Map.Entry<String, Integer>> iterator = entries.iterator();
        while (iterator.hasNext()) {
            //判断是否还有下一个可迭代的元素  打印输出
            Map.Entry<String, Integer> next = iterator.next();
            System.out.println(next.getKey() + "::" + next.getValue());
        }
    }
}

代码运行结果：

三、HashMap的实现

首先HashMap底层是数组+链表的数据结构，那么我们实现的时候，第一步就是实现对应的数组+链表。
属性及构造函数

class MyHashMap<K, V>{
    //定义哪些属性
    private int size; //有效节点个数
    private Node<K, V>[] table;//HashMap底层的桶  数组
    private static final int initalCapacity = 16;

    class Node<K, V> {   //节点
        protected K key;
        protected V value;
        protected Node<K, V> next;
        protected int hash;

        public Node(int hash, K key, V value) {
            this.hash = hash;
            this.key = key;
            this.value = value;
        }
    }
    //有哪些构造函数
    public MyHashMap() {
        this(initalCapacity);
    }

    public MyHashMap(int capacity) {
        table = new Node[capacity];
    }
    }
   

Hash函数
确定完基本数据结构之后，HashMap当然会用到hash函数，这里我们类比于HashMap中的hash函数，不单独实现代码如下：

//1.8中采用key的hashCode()异或上key的hashCode()进行无符号右移16位的结果
public int hash(Object key) {  //hash函数
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

方法实现(以put()方法为例)
要写代码，首先要确定思路，才能更好的写出代码，我们已经知道HashMap底层的数据结构，那么可以分析得到以下步骤实现put()方法，具体思路如下：

1）key-> hash(key) 散列码 -> hash & table.length-1 index
2）table[index] == null 是否存在节点
3）不存在   直接将key-value键值对封装成为一个Node 直接放到index位置
4）存在  注意key不允许重复，那么分为两种情况
5）存在 key重复       考虑新值去覆盖旧值
6）存在 key不重复     尾插法 将key-value键值对封装成为一个Node 插入新节点

代码实现如下：

public void put(K key, V value) {
        //key -》 h = hash(key)散列码 -》table.length-1 & h -> index（确定位置）
        //判断index位置是否存在节点
        //如果不存在，直接将当前key,value封装为一个Node,插入到该index位置
        //如果存在节点(保证HashMap中key不重复)
        //判断key是否重复
        //如果key有重复，考虑新值覆盖旧值
        //如果key没有重复，将当前key,value封装为一个Node 尾插法 插入当前index位置

        //key -》 h = hash(key)散列码 -》table.length-1 & h -> index（确定位置）
        int hash = hash(key);
        int index = table.length - 1 & hash;
        //判断index位置是否存在节点
        if (table[index] == null) {
            //如果不存在，直接将当前key,value封装为一个Node,插入到该index位置
            table[index] = new Node(hash, key, value);
            size++;
        } else {
            //如果存在节点(保证HashMap中key不重复)
            //获取该位置第一个节点
            Node<K, V> firstNode = table[index];
            if (firstNode.key.equals(key)) {
                firstNode.value = value;    //更新值
            } else {
                Node<K, V> tmp = firstNode;
                //判断key是否重复
                while (tmp.next != null && !tmp.key.equals(key)) {
                    //tmp一直跑，要么跑到最后一个节点，要么找到一个key与之相等的节点
                    tmp = tmp.next;
                }
                if (tmp.next == null) {
                    //跑到最后一个节点
                    if (tmp.key.equals(key)) {
                        //如果key有重复，考虑新值覆盖旧值
                        tmp.value = value;
                    } else {
                        //如果key没有重复，将当前key,value封装为一个Node 尾插法 插入当前index位置
                        tmp.next = new Node(hash, key, value);
                        size++;
                    }
                } else {
                    //如果key有重复，考虑新值覆盖旧值
                    tmp.value = value;
                }
            }
        }
    }

HashMap扩容
HashMap的扩容，是对数组进行二倍扩容，那么扩容完之后数组中每个链表节点即需要重新确定位置。

 int index = key % table.length(简化一下求index函数)
     原始链表长度为4
          0  1  2  3
     key  0     2
          4     6
          8
     新链表长度为8(2倍扩容)
          0 1 2 3 4 5 6 7
     key  0   2   4   6
          8
      观察分析可得：key=4 移到了 index=4 oldIndex+(newTable.length-oldTable.length) 0+4
                  key=6 移到了 index=2 oldIndex+(newTable.length-oldTable.length)  2+4
   那么可以得到结论：原来的结点要么在原位置，要么在 原位置+两表长度之差
     */

代码实现如下：

public void resize(){
        //HashMap的扩容
        //table进行扩容 2倍的方式 扩容数组
        Node<K, V>[] newTable = new Node[table.length*2];
        //index  -> table.length-1 & hash
        //重哈希
        for(int i=0; i<table.length; i++){
            rehash(i, newTable);
        }
        this.table = newTable;
    }

    public void rehash(int index, Node<K,V>[] newTable){
        //只是针对于数组中的某一个
        //index  当前要遍历哪一个位置点     index = key % table.length
        //给定新数组   重哈希到新数组
        //相当于对原先哈希表中每一个有效节点 进行 重哈希的过程
        Node<K,V> currentNode = table[index];
        if(currentNode == null){
            return;
        }

        Node<K,V> lowHead = null; //低位的头
        Node<K,V> lowTail = null;//低位的尾
        Node<K,V> highHead = null;//高位的头
        Node<K,V> highTail = null;//高位的尾

        while(currentNode != null){
            //遍历index位置的所有节点
            int newIndex = hash(currentNode.key) & (newTable.length-1);
            if(newIndex == index){
                //当前节点链到lowTail之后
                if(lowHead == null){
                    lowHead = currentNode;
                    lowTail = currentNode;
                }else{
                    lowTail.next = currentNode;
                    lowTail = currentNode;
                }
            }else{
                //当前节点链到highTail之后
                if(highHead == null){
                    highHead = currentNode;
                    highTail = currentNode;
                }else{
                    highTail.next = currentNode;
                    highTail = currentNode;
                }
            }
            currentNode = currentNode.next;
        }
        //要么在原位置 （低位位置）
        if(lowHead != null && lowTail != null){
            lowTail.next = null;
            newTable[index] = lowHead;

        }

        //要么跑到原位置 + 扩容前长度 （高位位置）
        if(highHead != null && highTail != null){
            highTail.next = null;
            newTable[index + table.length] = highHead;
        }
    }
}

文章不足之处，欢迎大家指正！后期附上源码链接撒！

本文地址：https://blog.csdn.net/m0_45177725/article/details/113359737