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
推荐阅读
-
java 面向对象的理解(简述java面向对象的三个基本特征)
-
Java语言基础之List集合以及Set集合的使用
-
java HashMap的keyset实例
-
java集合框架的体系结构详细说明
-
java中集合(LinkedList、HashSet、HashMap、HashTable、Collection、Collections)
-
java中Hashtable和HashMap的区别分析
-
基于Java中的数值和集合详解
-
Java中数组与集合的相互转换实现解析
-
java 集合并发操作出现的异常ConcurrentModificationException
-
Java 中初始化 List 集合的 6 种方式!