亲宝软件园·资讯

展开

Java集合类HashSet

世界尽头与你 人气:0

1.Set接口方法

Set接口对象存放的数据是没有重复,且数据是无序存放的(添加顺序和存放顺序不一致,但是这个存放的顺序是固定的,不会随机变化)

代码示例:

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

/**
 * Set接口方法
 */
public class SetTest {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        Set set = new HashSet();
        // 添加
        set.add("dahe");
        set.add("wangwei");
        set.add(521);
        set.add(521);
        set.add(null);
        System.out.println(set);
        // 遍历Set
        // 迭代器
        Iterator iterator = set.iterator();
        while (iterator.hasNext()) {
            Object obj =  iterator.next();
            System.out.println(obj);
        }
        // 增强for
        for (Object o : set) {
            System.out.println(o);
        }
    }
}

2.HashSet

HashSet的底层其实,是HashMap:维护的是一个数组 + 单向链表

public HashSet() {
    map = new HashMap<>();
}

HashSet不保证存放元素的顺序和取出的顺序一致,这取决于hash后,再确定索引的结果

代码示例:

import java.util.HashSet;
import java.util.Set;

/**
 * HashSet
 */
public class HashSetText {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        Set hashSet = new HashSet();
        // 添加
        hashSet.add("dahe");
        // 添加成功,返回true,失败返回false
        System.out.println(hashSet.add("qian"));
        System.out.println(hashSet.add("qian"));
        System.out.println(hashSet);
        // 添加对象,以下是不同的对象
        hashSet.add(new DDD("aaa"));
        hashSet.add(new DDD("aaa"));
        System.out.println(hashSet);
        // 经典面试题,以下的两个只能添加一个
        hashSet.add(new String("hsp"));
        hashSet.add(new String("hsp"));
        System.out.println(hashSet);
    }
}

class DDD {
    private String name;

    public DDD(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return "DDD{" +
                "name='" + name + '\'' +
                '}';
    }
}

3.HashSet的扩容机制 - 初次添加数据

针对如下的代码对java的扩容机制进行分析:

hashSet.add("dahe");
System.out.println(hashSet.add("qian"));
System.out.println(hashSet.add("qian"));

执行add操作:(传入待添加的值e和PRESENT,这里的PRESENT只起到一个占位的效果)

private static final Object PRESENT = new Object();
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

继续步入:

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

在进入putVal方法之前,我们先来看一下这个hash的算法:

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

如果待添加的数据为null,则返回0值,否则返回hash算法的结果(此算法可以极大的防止冲突的发生)

执行putVal方法:这个方法很重要(且复杂)!

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        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) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        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;
}

不要慌,我们来一步一步进行分析:

先来看一下这个东西:

Node<K,V>[] tab;

这个是存放Map Node节点的数组,如果你精通数据结构邻接表,对这个数组应该很熟悉,tab里面的存储结构是这样的:(下图仅作示例)

当这个节点数组为空或者大小为0的时候,会触发这个操作:(tab先进行resize操作,随后返回给n一个处理后数组的大小)

if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;

那这个resize操作到底是什么呢?我们步入来看看它的真面目:

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

由于初始化tab为null,经过一番操作,会执行如下的代码,这里给计算了新数组的空间大小:

newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

DEFAULT_INITIAL_CAPACITY的定义,默认表的大小为16:

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

下面这里是JDK设计者的聪明所在,tab数组并非用到空之后扩容,而是内部有一个临界的值newThr,所用的空间达到临界的值会触发扩容机制 (容量*2),起到一个缓冲的效果,这样做主要是为了防止阻塞

注意:这里的空间指的是全部节点的数量,而非tab元素的个数

newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

一切准备就绪,开始扩容(这里初始化扩容的tab容量为16):

Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;

我们再回到putVal方法,看一下接下来会发生什么有趣的事情

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

根据key得到hash,去计算该key应该存放到table表的那个索引位置,并把这个位置对象赋值给p,如果p为null的话,表示该索引位置还没有存放过任何的数据,就在tab[i]位置创建一个Node,创建完新Node之后,它在tab数组中的存储结构就变成了这样:

继续向下走,修改次数 + 1,并且还要判断一次tab元素数量是否大于了临界值,如果大于了临界值,进行扩容操作:

++modCount;
if (++size > threshold)
    resize();

最后,返回null,代表一切操作成功!

至此,初次添加数据的操作就已经完成了!

4.HashSet的扩容机制 - 继续添加数据

初次添加数据的结构其实很简单,更加困难的是第二次添加数据的操作

我们继续步入,再次追到putVal方法:

和初次添加不同的是,不会再进入下面的语句,而是向下执行:

if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;

直接判断计算得出的tab索引位置有没有数据,没有的话(实验的值没有)继续新建节点:

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

添加完数据后,tab里面的结构就变成了这样:

5.HashSet的扩容机制 - 添加重复元素

此时存在两个key是相等的,那么下面的语句必然不会为空,因为key相等,那么他们hash过后的值也会相等:

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

继续步入,走到else里面,我们来看一下if语句里面的内容:

if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k))))
    e = p;

如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样

并且满足准备:(比较地址和值)

这时就不能加入,执行:e = p;

再来看看else if语句:

判断p是不是一颗红黑树,如果是的话就按照红黑树的方式进行比较:

else if (p instanceof TreeNode)
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

再看看else语句:

for (int binCount = 0; ; ++binCount) {
    if ((e = p.next) == null) {
        p.next = newNode(hash, key, value, null);
        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            treeifyBin(tab, hash);
        break;
    }
    if (e.hash == hash &&
        ((k = e.key) == key || (key != null && key.equals(k))))
        break;
    p = e;
}

当前索引位置已经是一个链表。会依次和该链表的每一个节点进行比较,有重复的直接break掉,没有重复的进行挂载

注意:在添加新节点之后,需要进行一次链表长度判断,看下当前链表中是否已经有8个节点了,如果已经存在了8个节点,会通过treeifyBin方法尝试进化链表为红黑树

有趣的是,在进化红黑树的代码中,存在下面这两行:

if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    resize();

这里面的MIN_TREEIFY_CAPACITY定义如下:

static final int MIN_TREEIFY_CAPACITY = 64;

也就是说,如果tab长度小于64,不会马上进行树化,会先进行tab扩容操作!

加载全部内容

相关教程
猜你喜欢
用户评论