欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

JAVA集合——HashMap的简述

程序员文章站 2022-10-03 10:11:11
一、HashMap的底层数据结构数组:对于数组而言,可以根据所找值的索引直接查找该值的位置,即查找容易,删除插入不易。链表:对于链表而言,查找不易,删除插入容易。红黑树:自平衡二叉查找树而哈希表便是对两种基础数据结构的结合,作为一个查找容易,插入删除也容易的数据结构。哈希表又称为散列表,是根据关键码key直接访问内存存储位置的数据结构,即通过关于key的函数,映射到一个地址来访问数据,这样来加快查找速度。在JDK1.8之前,是数组加链表,在JDK1.8之后,二、HashMap的使用三、Hash...

首先附上HashMap结构图一张,方便大家更好的认其底层数据结构,本篇博客主要是对HashMap基本知识以及如何实现HashMap的总结。
JAVA集合——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());
        }
    }
}

代码运行结果:
JAVA集合——HashMap的简述

三、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