文章目录
- 一、HashMap
- 1-1 底层实现
- 1-2 属性解读
- 1-3 put方法核心流程
- 1-4 和TreeMap的区别
- 二、HashSet
- 2-1 底层实现
- 2-2 去重原理
提示:以下是本篇文章正文内容,Java系列学习将会持续更新 一、HashMap 1-1 底层实现
-
JDK7之前的HashMap就是一个基于开散列的散列表实现,数组+链表的结构。
可以查看之前的文章:Java数据结构之哈希表 -
JDK8之后引入了红黑树。当某个链表的长度过长时,元素的查询退化为链表的遍历,O(1) - 》O(N)。此时将链表树化,查询效率起码也是O(logN)。
默认哈希表的长度
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
最大容量为 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
负载因子为0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
链表最大长度为8,超过则扩容 / 树化
static final int TREEIFY_THRESHOLD = 8;
当链表长度超过8,且总节点数超过64时,才进行树化
static final int MIN_TREEIFY_CAPACITY = 64;
解树化,当RBTree的节点数小于该值时,退化为链表
static final int UNTREEIFY_THRESHOLD = 6;
哈希运算
static final int hash(Object key) { int h; // 为何取出key值得高16位右移参与hash运算? // 这样高16位和低16位的异或运算,尽量保证数据均匀分布。 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
1-3 put方法核心流程Java 中计算哈希值实际上是调用的类的 hashCode 方法,进行 key 的相等性比较是调用 key 的 equals 方法。
所以如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值,必须覆写 hashCode 和 equals 方法,而且要做到 equals 相等的对象,hashCode 一定是一致的。
- 若HashMap还未初始化,先进行哈希表的初始化操作(默认初始化为16个桶)
- 对传入的key值做hash,得出要存放该元素的桶编号
a.若没有发生碰撞,即头结点为空,将该节点直接存放到桶中作为头结点
b.若发生碰撞
1.此桶中的链表已经树化,将节点构造为树节点后加入红黑树
2.链表还未树化,将节点作为链表的最后一个节点入链表 - 若哈希表中存在key值相同的元素,替换最新的value值
- 若桶满了(rize++ 是否大于threshold),调用resize()扩容哈希表。
thresholed = 容量(默认16) * 负载因子 (默认0.75)
-
HashMap基于哈希桶实现。TreeMap基于红黑树实现。
-
HashMap无序,TreeMap有序。
-
HashMap的工作效率更高,O(1)。而TreeMap则是基于树的增删查改,O(logN),更推荐使用HashMap。
-
HashMap的 key和value 都可以为 null。TreeMap 的 key 不可以为 null,value 可以为 null。
-
两者都不是线性安全的。
回到目录…
二、HashSet 2-1 底层实现Java中的Set的实现实际上就是依托了Map的实现。
也就是说,HashSet 就等于 HashMap,TreeSet 就等于 TreeMap。
看看源码:
看看源码:
public boolean add(E e) { // HashSet也是可以存 null 的 return map.put(e, PRESENT)==null; }
面试题:为什么Set可以去重?底层是如何实现的?
因为 HashSet 的底层实现实际上就是内置了一个 HashMap,元素是存储在 map 表上,只不过 value 上是一个静态的 Object 类。
所以就和 HashMap 的插入一样,key 不可以重复。
当我们在 map 中插入元素的时候,根据 hashCode() 方法计算出桶的位置,在遍历桶中的元素,用 equals() 方法逐一比较,最终就可以知道元素是否存在, 到底需要插入还是更新。在返回原来的value值时,如果为 null,说明插入成功,对应到 set 中,就返回了 true。
回到目录…
总结:
提示:这里对文章进行总结:
以上就是今天的学习内容,本文是Java数据结构的学习,扒开JDK的源码,看看Map和Set底层是如何实现的,它们之间有什么的关系。之后的学习内容将持续更新!!!