【Java】Java集合框架源码和数据结构简要分析——Set和Map

时间:2022-03-02 10:37:44

前言

        之前一直把集合框架分成Collection和Map来对待,主要是基于储存内容是单列和双列,实际上这样来区分不太正确,set实际上是双列的结构。

        现在回顾集合框架,看到很多当初看不到的东西。

        现在来看集合框架,一部分是List,一部分是Set和Map,Set和Map几乎就是一回事。

        本文假设你已经对集合框架有一定了解,关于细节请看《集合框架和Map基础》


一、数据结构

        不讲太深入的东西,实际上我也讲不了多深入。

        数据结构,就是一堆数据的关系。

        逻辑结构——数据逻辑上的关系,其实就是数据结构,而数据的逻辑结构几乎可以分成四种:线性结构、集合结构、树形结构和图结构。

        物理结构——上述四种逻辑结构,无论哪一种,最终都是要保存到物理内存中,也就是逻辑结构的基础是物理结构,而数据的物理结构无外乎两种:顺序存储结构和链式存储结构。顺序存储结构,常见的就是数组,需要一片连续的内存;链式存储结构,不需要连续内存,但是前一个数据对象需要关联下一个数据对象的内存地址。


二、HashSet和HashMap

        HashSet的底层是HashMap,HashMap的底层有数组、链表和自平衡二叉树,但主要是数组,因此HashSet和HashMap是一回事(不信稍后看源码),而且主要基于顺序存储结构。

1. 关系

        HashSet里面使用了HashMap,不过只是使用了他的key,每次向set中存放数据的时候,都是存放在key上,而value上则所有一律存储的是一个private static final Object object对象。

public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
static final long serialVersionUID = -5024744406713321676L;
//HashSet使用了HashMap,所有的value实际上都是存放在map的key位置
private transient HashMap<E,Object> map;
//而value则一律都是一个static final的Object对象PRESENT
private static final Object PRESENT = new Object();

public HashSet() {
map = new HashMap<>();
}
//添加元素
//元素在key位置,而map的value位置是一个永远不会改变的Object对象
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
}

        而HashMap中的KV实体是主要存放在数组结构中。

public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
private static final long serialVersionUID = 362498820763181265L;
//实际上一个KV被包装成一个Node,而所有的Node都被存放在table数组中
transient Node<K,V>[] table;

//Map的KV结构定义
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;

Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
//方法省略
}
}

2. 哈希

        哈希为什么快?在前期给定的数组大小足够的情况下,他的增删改查性能都是O(1),其主要是一个hash方法,将对象的特征值映射到一个数组下标,重点是不同对象根据哈希方法产生的映射值不同,否则就会退化成链表的性能。原理讲起来几句话,但是最关键的哈希方法的实现,得是算法工程师们研究的内容了。我底蕴不够,讲不了太多。

        还是顺带补一嘴,哈希的关键方法hashCode和equals,这些属于基础知识,请自行了解,谢谢。

        HashMap实现的哈希方法,只是产生哈希值,最终映射数组下标在put方法中完成,这一部分请查看第三小节,链表和二叉树中贴出的源码。

static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

3. 链表和二叉树

        既然是基于数组,那么避免不了动态扩容。HashMap源码有动态扩容内容,请自行观赏源码,而且JDK8中的Hash对于哈希冲突问题,不再仅仅是使用链表来解决(这里是采用单链表,不像LinkedList采用的是双链表),还根据冲突演变到一定规模,会采用自平衡二叉树来替代链表来获取更好的性能,从时间复杂度O(n)提升到了O(logn)。这里源码太多不好讲,还是老话,自行观赏源码(下面节选插入的部分核心源码),哈哈~

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//将table的引用赋值给tab
//如果是第一次放入KV元素,那么就初始化一下table
//n=初始化完成后table的length
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//传进来的hash已经经过一次计算
//将hash值映射到数组下标并赋值给p
//如果该位置还未被分配,则新加入的KV被封装成Node并存放与该位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//如果这个位置已经分配了,那么就出现哈希冲突,需要解决冲突问题
else {
Node<K,V> e; K k;
//如果该位置上已有的Node哈希值和当前传入Key的哈希值(注意区别,hash()方法)相同
//并且key也相同
//说明是同一个key,那么就不是新加入KV,而是替换老的value
//这里只是将老的Node p赋值给e,修改value在方法最后
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//哈希冲突,进入自平衡二叉树(红黑树)逻辑,根据哈希值来做左右孩子的判定
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//哈希冲突,进入链表逻辑
else {
for (int binCount = 0; ; ++binCount) {
//如果该位置是第一次出现哈希冲突,那么将新的KV封装成node,放在老的Node后面,挂成链表
if ((e = p.next) == null) {
//链表解决冲突问题
p.next = newNode(hash, key, value, null);
//如果同一位置上出现哈希冲突的规模达到阈值TREEIFY_THRESHOLD-1(7)
//那么将链表转成自平衡二叉树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果是链表上存在的老Node,那么也是赋值一下,最后在替换value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//如果是老Node,那么就替换value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}

4. 增删改查

        至于其增删改查性能,基于哈希,在不计较动态扩容的前提下,都是O(1),但是如果产生哈希冲突,则会局部损失性能至链表或自平衡二叉树,但是自平衡二叉树的性能是比链表要好的,这是JAVA 8代码优化上做的性能提高。


三、TreeSet和TreeMap

        TreeSet是基于TreeMap,TreeMap的底层是链式存储结果,逻辑结构是树,自平衡二叉树,或者说红黑树。

1. 关系

        TreeSet通过装饰器模式来使用TreeMap,他们两个实现了相同的接口NavigableMap,而在TreeSet中则持有NavigableMap的引用,实际上构造TreeSet的时候会new TreeMap出来。

public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
{
private transient NavigableMap<E,Object> m;
//最终不管哪一个构造方法被调用,最终都是转调该构造方法,完成TreeMap的初始化
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
public TreeSet() {
this(new TreeMap<E,Object>());
}
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}
public TreeSet(Collection<? extends E> c) {
this();
addAll(c);
}
public TreeSet(SortedSet<E> s) {
this(s.comparator());
addAll(s);
}
}
        再看TreeMap中的链表结构定义,Entry,它其中的left和right分别表示左孩子和右孩子。

static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;

/**
* Make a new cell with given key, value, and parent, and with
* {@code null} child links, and BLACK color.
*/
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}

/**
* Returns the key.
*
* @return the key
*/
public K getKey() {
return key;
}

/**
* Returns the value associated with the key.
*
* @return the value associated with the key
*/
public V getValue() {
return value;
}

/**
* Replaces the value currently associated with the key with the given
* value.
*
* @return the value associated with the key before this method was
* called
*/
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}

public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;

return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
}

public int hashCode() {
int keyHash = (key==null ? 0 : key.hashCode());
int valueHash = (value==null ? 0 : value.hashCode());
return keyHash ^ valueHash;
}

public String toString() {
return key + "=" + value;
}
}

2. 关于排序

        实现排序,都只是针对key而言(Set只是用了Map的key),可以通过自然排序(集合框架中存储的对象实现了Compareble接口,自身具有比较性)和定制排序(集合框架自己有比较器,实现Compartor接口),这里也是基础知识部分,请参看 《集合框架和Map基础》,此处不再赘述。


四、性能比较

        其实性能比较,比较的是哈希和红黑树的性能,哈希性能显然占优(接近于O(1),而红黑树则是O(logn)),但是哈希虽然快但是元素无序,红黑树虽然慢一点但是能实现有序,具体还是根据业务场景来看吧。


附注:

        本文如有错漏,烦请不吝指正,谢谢!

        熬夜写的,思路已经不是很清晰鸟,见谅~