JavaSE-集合（Set）

Set
- HashSet 实现类
- LinkHashSet
- TreeSet

Set

基本API

public class Demo6 {
    public static void main(String[] args) {
        
        Set set = new HashSet();
        set.add(12);
        set.add(1);
        set.add(9);
        set.add(30);
        set.add(12);
        set.add(8);
        System.out.println(set.contains(12));  //=> true
        System.out.println(set.hashCode());  //=> 60
        System.out.println(set.size());  //=> 5
        Iterator iterator = set.iterator();
        while (iterator.hasNext()){
            System.out.print(iterator.next()+"t");  //=> 1	8	9	12	30
        }
    }
}

HashSet 实现类

特点：唯一且无序。

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

class Test{
    public int num;
    public String str;

    public Test(int num, String str) {
        this.num = num;
        this.str = str;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Test)) return false;
        Test test = (Test) o;
        return num == test.num && str.equals(test.str);
    }

    @Override
    public int hashCode() {
        // 获取哈希码
        return Objects.hash(num, str);
    }

    @Override
    public String toString() {
        return "Test{" +
                "num=" + num +
                ", str='" + str + ''' +
                '}';
    }
}
public class Demo4 {
    public static void main(String[] args) {
        Set set = new HashSet();
        set.add(120);
        set.add(212);
        set.add(1);
        set.add(1);
        set.add(450);
        set.add(511);
        System.out.println(set); //=> [1, 2, 3, 4, 5]
        System.out.println(set.size());  //=> 5

        Set set2 = new HashSet();
        set2.add("hello");
        System.out.println(set2.add("world"));  //=> true
        System.out.println(set2.add("world"));  //=> false
        System.out.println(set2);  //=> [world, hello]
        System.out.println(set2.size());  //=> 2

        Set set3 = new HashSet();
        set3.add(new Test(12,"XIAOMING"));
        set3.add(new Test(13,"XIAOHUA"));
        set3.add(new Test(13,"XIAOMING") );
        System.out.println(set3.add(new Test(12, "XIAOMING"))); //=> false
        System.out.println(set3);  //=> [Test{num=13, str='XIAOHUA'}, Test{num=13, str='XIAOMING'}, Test{num=12, str='XIAOMING'}]
        System.out.println(set3.size());  //=> 3
    }
}

源码分析：

经过上述测试发现放入String，Integer类型的数据都没有问题，都遵照HashSet的特点，但是放入自定义引用类型数据就不行了？解决：自定义类必须重写equals、hashCode方法。

底层原理分析：以Integer 为例

注意当链表的长度大于7时，链表会变成红黑树，提高查询效率。

1. 数据是如何以链表的方式进行储存的？底层原理又是什么？

计算哈希码（调用hashCode()，结果返回的是一个int 类型的数据，integer类型的哈希码取自身即可）。
计算主数组存储位置 y=k(x)=x%11 x 表示哈希码 k(x) 函数 y 就是存储位置
放入哈希表

（1）一次添加成功（结果都是true，创建新节点，存储数据，被加入到链表末尾）

（2）多次添加成功（出现重复，会调用equals()和对应的链表元素进行比较，比较到最后是false，不添加）
结论：

（1）添加数据执行三步即可

（2）唯一

（3）无序
底层原理：HashMap 对象

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

add 方法

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

2. hashCode(), equals() 执行几次？

存入多少元素就执行多少次hashCode()
在相同位置上存入元素的时候才会执行equals()

3. 各种类型的hashCode 返回值是什么？

Integer

    public int hashCode() {
        return Integer.hashCode(value);
    }

String

    public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

"abc"
h = 31*0+97 = 97
h = 31*97+98 = 3105
h = 31*3105+99 = ...
---> h 哈希码

类对象

public stataic int hashCode(Object a[]){
	if(a==null){
		return 0;	
	}
	int result = 1;
	for(Object element : a){
		result = 31 * result + (element == null ? 0 : element.hashCode());
	}
	return result;
}

4. 底层的计算位置表达式一定是取余吗？

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

5. 底层主数组长度是多少？

初始数组长度为16

// from HashMap

    final Node[] resize() {
        Node[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;				//----0
        int oldThr = threshold;				//----0
        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;				//----16
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);				//----12
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;				//----12
        Node[] newTab = (Node[])new Node[newCap];				//----长度 16 的数组
        table = newTab;  // 长度为16的主数组
        if (oldTab != null) {
        	// 扩容后的数组对原数组进行转移
            for (int j = 0; j < oldCap; ++j) {
                Node 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)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node loHead = null, loTail = null;
                        Node hiHead = null, hiTail = null;
                        Node 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;
    }

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
    }

6. 底层是否进行数组的扩容？

会，当szie 大于数组承载数量且小于最大值时会进行数组扩容，初始的数组承载量为

newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//16*0.75=12
threshold = newThr;

数组长度为16

newCap = DEFAULT_INITIAL_CAPACITY;  //16
Node[] newTab = (Node[])new Node[newCap];

进行扩容：数组长度 16<<1 ，承载量 12<<1

int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold

7. 主数组的类型是什么？

主数组时Node 对象类型数据：

static class Node implements Map.Entry {
        final int hash;
        final K key;
        V value;
        Node next;

        Node(int hash, K key, V value, Node next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry e = (Map.Entry)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

8. 数组中的链表是什么样的，结点内容有什么？

static class Node implements Map.Entry {
        final int hash;
        final K key;
        V value;
        Node next;

        Node(int hash, K key, V value, Node next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry e = (Map.Entry)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

9. 链表是如何追加元素的，在哪加？

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node 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 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)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);   /
        TreeSet treeSet = new TreeSet();
        treeSet.add(12);
        treeSet.add(1);
        treeSet.add(9);
        treeSet.add(30);
        treeSet.add(12);
        treeSet.add(8);
        System.out.println(treeSet);  //=> [1, 8, 9, 12, 30]
        System.out.println(treeSet.ceiling(5));  //=> 8,返回此set中大于或等于给定元素的 null元素，如果没有这样的元素，则 null 。
        System.out.println(treeSet.descendingSet());  //=> [30, 12, 9, 8, 1],以降序返回此集合中元素的迭代器。
        System.out.println(treeSet.first());  //=> 1,返回此集合中当前的第一个（最低）元素。
        System.out.println(treeSet.floor(10));  //=> 9,返回此set中小于或等于给定元素的最大元素，如果没有这样的元素，则 null 。
        System.out.println(treeSet.higher(10));  //=> 12,返回此set中的最小元素严格大于给定元素，如果没有这样的元素，则 null 。
        System.out.println(treeSet.lower(10));  //=> 9,返回此set中的最大元素严格小于给定元素，如果没有这样的元素，则 null 。
        System.out.println(treeSet.headSet(10));  //=> [1, 8, 9],返回此set的部分视图，其元素严格小于 toElement 。
        System.out.println(treeSet.subSet(10, 30));  //=> [12],返回此set的部分视图，其元素范围从 fromElement （含）到 toElement （独占）。
        System.out.println(treeSet.subSet(10, true, 30, true));  //=> [12, 30],返回此set的部分视图，其元素范围为 fromElement到 toElement 。
        System.out.println(treeSet.tailSet(30));  //=> [30],返回此set的部分视图，其元素大于或等于 fromElement 。
        System.out.println(treeSet.tailSet(30, false));  //=> []
        System.out.println(treeSet.tailSet(30, true));  //=> [30],返回此set的部分视图，其元素大于（或等于，如果 inclusive为true） fromElement 。
    }
}

JavaSE-集合（Set）

Java相关栏目本月热门文章