【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)），但是哈希虽然快但是元素无序，红黑树虽然慢一点但是能实现有序，具体还是根据业务场景来看吧。


附注：

        本文如有错漏，烦请不吝指正，谢谢！

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

标签：

相关文章