2021-04-12

2023-12-26 19:54:57

HashMap集合

1. HashMap介绍
2. HashMap方法原理
3. HashMap用法简单使用

1. HashMap介绍

1.1 HashMap的简介

HashMap是Map集合接口的子类之一，是常用的Map之一。
HashMap是以 key-value 的形式存储数据的。允许key为null，但只允许一个key为null；允许value为null。
HahMap中key不能重复，value可以重复。
HashMap的初始容量为16，默认加载因子为0.75。
HashMap是线程不安全的。

1.2 HashMap的数据结构（1.7和1.8）

JDK1.7时的数据结构是数据 + 链表
当要put数据是，先会计算key的hash值，存放到相应的数组索引位置，如果当前位置没有值，则直接存储；如果当前位置上有值，则调用重写的equals方法比较key，如果相同则覆盖value，如果不同则说明是不同的值则插入到链表的头部

JDK1.8时的数据结构是数据 + 链表 + 红黑树
在1.8中，hashMap在new的时候不会初始化容量，只有当put的时候才会进行初始化
HashMap 在 Java 8 中的实现增加了红黑树，当链表节点达到 8 个的时候，会把链表转换成红黑树，低于 6 个的时候，会退回链表。究其原因是因为当节点过多时，使用红黑树可以更高效的查找到节点。毕竟红黑树是一种二叉查找树。

1.4 HashMap需要同时重写hashCode方法和equals方法的原因？

hashCode和equals方法是Object中的原生方法:
equals：比较的是对象的地址值是否相等
hashcode（）：返回的是对象的地址，所以这种情况下不同对象的hashcode肯定不同

为什么要重写hashCode方法
hashMap.put(“a”,“123”) ，hashMap.put(“a”,“123”)时；如果不重写hashcode，那么同样的一个键值对，唯一性得不到保证，所以一定要重写hashCode方法。因为Object的hashcode返回的是内存地址，可能造成的存储结果如下：

0	1	2	3	4	5
(“a”,“123”)		(“a”,“123”)

为什么要重写equals方法：
hashMap.put(“a”,“123”) ，hashMap.put(“b”,“123”)时；两次put元素的hash值相同，则会用链表的方式存储，存储形式如下：

0	1	2	3	4	5
(“a”,“123”)
(“a”,“123”)

当要get(“a”)时，会进行hashCode判断，知道去索引为0的位置查找，就会发现有2个元素，此时就无法判断要取出的数据为哪个。所以必须要重写equals方法才能判断对象的值

总结：
hashCode相同，值不一定相同；hashCode不同，值一定不同
hashCode保证键的唯一性，equals保证值的唯一性，所以需要同时重写

2. HashMap方法原理

2.1 put方法

put的过程：

1：对key的hashCode() 做hash计算，然后根据hash值再计算Node的存储索引位置。
2：检查当前数组是否为空，为空就进行初始化，初始化容量为16，默认加载因子为0.75
3：如果没有哈希碰撞，直接放入桶中；如果有哈希碰撞，比较equals方法，判断是否相同，如果相    同则替换value；不同则以链表的形式存入尾部
4：如果哈希碰撞导致链表长度大于8，则将链表转为红黑树
5：当桶数量超过 容量*负载因子 时，就进行扩容，扩容为原数组长度的两倍

2.2 get方法

get方法的过程：

对 key 的 hashCode() 做 hash 计算，然后根据 hash 值再计算桶的 index
如果桶中的第一个节点命中，直接返回；
如果有冲突，则通过 key.equals(k) 去查找对应的 entry
    若为树，则在红黑树中通过 key.equals(k) 查找，O(logn)；
    若为链表，则在链表中通过 key.equals(k) 查找，O(n)。

2.3 HashMap的扩容机制

数组容量是有限的，数据多次插⼊的，到达⼀定的数量就会进⾏扩容，也就是resize。
影响resize有两个因素：
Capacity：HashMap当前⻓度。
LoadFactor：负载因⼦，默认值0.75f。

    /**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

就⽐如当前的容量⼤⼩为100，当你存进第76个的时候，判断发现需要进⾏resize了，那就进⾏扩容。
扩容的步骤
分为两步
扩容：创建⼀个新的Entry空数组，⻓度是原数组的2倍。
ReHash：遍历原Entry数组，把所有的Entry重新Hash到新数组。
需要重新Hash的原因：
是因为⻓度扩⼤以后，Hash的规则也随之改变。
Hash的公式—> index = HashCode（Key） & （Length - 1）

3. HashMap用法简单使用

public static void main(String[] args) {
		HashMap<String,String> hm=new HashMap<String,String>();
		
		hm.put("it001", "lh");
		hm.put("it003", "dc");
		hm.put("it004", "ch");
		hm.put("it002", "dc");
		hm.put("it001", "lhh");//键的唯一性
		hm.put("it005","lh");
		hm.put("dc","lh");
		hm.put("中","lh");
		
		System.out.println(hm);
		//输出结果
		//{it004=ch, it003=dc, it005=lh, it002=dc, it001=lhh, 中=lh, dc=lh}
		
		System.out.println(hm.get("it001"));//lhh 
		System.out.println(hm.get("it002"));//dc 
		
		//遍历输出
		Set<String> set=hm.keySet();
		for(String key:set) {
		   String value=hm.get(key);//键找值
		   System.out.println(key+"---"+value);
		}
	}

允许key为null，但只允许一个key为null；允许value为null。

public static void main(String[] args) {
		HashMap<String,String> hm=new HashMap<String,String>();
		hm.put(null, "word");
		hm.put("word", "word");
		hm.put("wor", null);
		hm.put(null, null);
		
		System.out.println(hm);//{null=null, wor=null, word=word}
		
	}

以上就是对HashMap的一个理解，如果有问题感谢提出，一起进步。

码农公寓