乘风原创程序

  • JAVA集合——HashMap的简述
  • 2021/2/23 10:14:55
  • 首先附上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