Set接口

Set接口

Set接口及其实现类

• Java集合
• • java容器
• 集合
• • 常见的集合
• Collection集合
• • Set接口
  • • 相应实现类的源码分析
    • • HashSet
    • TreeSet
    • • TreeSet遍历

Java集合 java容器

即集合、数组都是对多个数据进行存储 *** 作的结构

集合

集合是存放数据对象引用的容器，集合可以避免数组的缺点

常见的集合

List列表，Set集合，Map映射

Collection集合

Collection接口是集合类的根接口，Java中没有提供这个接口的直接的实现类。却让其被继承，所以产生了两个接口，就是Set和List

Set接口

Set接口：元素无序，不可重复的集合 ，并且最多包含一个null元素
        |--HashSet:作为Set接口的主要实现类；线程不安全；可以存储null值
                |--linkedHashSet:作为HashSet子类:遍历其内部数据时，可以按照添加的顺序遍历
        |--TreeSet:可以按照添加元素的指定属性进行排序

相应实现类的源码分析 HashSet

//无参构造器，由此可知，HashSet底层是HashMap
public HashSet() {
        map = new HashMap<>();
    }
//增
 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);
    }
    
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        //tab引用当前HashMap的散列表
        //p是当前散列表的元素
        //n是散列表数组的长度
        //i是路由寻址((length-1)&hash) 结果
        Node[] tab; Node p; int n, i;
        //第一次调用putVal时初始化hashMap对象中的散列表
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //如果通过路由算法得到的在数组中的该位置为null，则直接添加key-value(在此对p进行了赋值)
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            //e是临时的元素，不为null，找到了一个与要插入的key-value一致的key的元素
            //k是元素的key
            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 {
                //链表，而且当前链表的头元素与插入元素的key不一致
                for (int binCount = 0; ; ++binCount) {
                    //条件成立的话，迭代到最后一个元素也没有找到与插入元素key相同的元素，即将该元素插入到链表末尾
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //条件成立的话，说明当前链表的长度达到树化的标准，需要进行树化
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            //树化 *** 作
                            treeifyBin(tab, hash);
                        break;
                    }
                    //条件成立的话，说明找到了相同key的元素，需要进行替换 *** 作
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //条件成立，说明找到了一个与插入元素key完全一致的数据进行替换
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        //表示散列表结构被修改的次数，替换元素的value不计数
        ++modCount;
        //插入新元素，size自增，若自增后大于扩容阈值，则触发扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
//删
public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }
public V remove(Object key) {
        Node e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }
 final Node removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node[] tab; Node p; int n, index;
        //盘算判断table数组不能为空且长度大于0并进行相应赋值，并且key相对应的索引处数组不为空
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node node = null, e; K k; V v;
            //如果要删除的key值和p节点的key值相等的话(hash相等，key相等或者equals结果相等)
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                //把p节点赋值给node变量
                node = p;
            //否则就取得p的后继节点，并赋值给e变量，看下e是不是为null，不为null的话
            else if ((e = p.next) != null) {
                //如果p节点类型已经是树节点类型了
                if (p instanceof TreeNode)
                    //就通过getTreeNode()方法去树中取得相应节点，并赋值给node变量
                    node = ((TreeNode)p).getTreeNode(hash, key);
                else {
                    //链表结构
                    do {
                        //如果要删除的key值和e节点的key值相等的话(hash相等，key相等或者equals结果相等)
                       if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            //找到对应的删除结点
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                //树类型的话，调用removeTreeNode()删除结点
                if (node instanceof TreeNode)
                    ((TreeNode)node).removeTreeNode(this, tab, movable);
                //删除首结点
                else if (node == p)
                    tab[index] = node.next;
                //删除一般结点
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        //如果找不到删除结点返回null
        return null;
    }

TreeSet

注意：Set 接口是按照 equals  *** 作定义的，但 TreeSet 实例使用它的 compareTo（或 compare）方法对所有元素进行比较

//构造器之一，可以知道TreeSet基于TreeMap
public TreeSet() {
        this(new TreeMap());
    }
//增
public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }
//调用TreeMap的put()
public V put(K key, V value) {
        Entry t = root;
        //根节点为空，直接插入
        if (t == null) {
            compare(key, key); // type (and possibly null) check

            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry parent;
        // 自定义比较器不为空时，使用自定义比较器
        Comparator cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left; //向左转
                else if (cmp > 0)
                    t = t.right;  //向右转
                else
                    return t.setValue(value);  //找到相同的
            } while (t != null);
        }
        //自定义比较器为空时，使用自然排序
        else {
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                Comparable k = (Comparable) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;//向左转
                else if (cmp > 0)
                    t = t.right;  //向右转
                else
                    return t.setValue(value);  //找到相同的
            } while (t != null);
        }
        Entry e = new Entry<>(key, value, parent);//创建新entry
        if (cmp < 0)
            parent.left = e;//插左边
        else
            parent.right = e;//插右边
        //插入后再次调整为红黑树
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }
//删
public boolean remove(Object o) {
        return m.remove(o)==PRESENT;
    }
//TreeMap的remove()
public V remove(Object key) {
        //找到key对应的entry
        Entry p = getEntry(key);
        if (p == null)
            return null;

        V oldValue = p.value;
        //删除相应的entry
        deleteEntry(p);
        return oldValue;
    }
// 红黑树entry删除函数deleteEntry()
private void deleteEntry(Entry p) {
        modCount++;
        size--;
        //  如果点p的左右子树都非空
        if (p.left != null && p.right != null) {
            Entry s = successor(p);// 后继
            p.key = s.key;
            p.value = s.value;
            p = s;
        } // p has 2 children

        // Start fixup at replacement node, if it exists.
        Entry replacement = (p.left != null ? p.left : p.right);
		//  删除点p只有一棵子树非空。
        if (replacement != null) {
            // link replacement to parent
            replacement.parent = p.parent;
            if (p.parent == null)
                root = replacement;
            else if (p == p.parent.left)
                p.parent.left  = replacement;
            else
                p.parent.right = replacement;

            // Null out links so they are OK to use by fixAfterDeletion.
            p.left = p.right = p.parent = null;

            // Fix replacement
            if (p.color == BLACK)
                fixAfterDeletion(replacement);
        } else if (p.parent == null) { // return if we are the only node.
            root = null;
        } else { //  删除点p只有一棵子树非空。
            if (p.color == BLACK)
                fixAfterDeletion(p);

            if (p.parent != null) {
                if (p == p.parent.left)
                    p.parent.left = null;
                else if (p == p.parent.right)
                    p.parent.right = null;
                p.parent = null;
            }
        }
    }

• TreeSet实现了Set类，也是不可以存储存储重复的元素
• 没有索引，但是可以将元素按照规则进行排序
  • TreeSet()：使用无参构造根据其元素的自然排序进行排序
    • 实现Comparable接口，重写comparaTo方法
  • TreeSet(new Comparator )：根据指定的比较器进行排序
    • 实现Comparator接口，重写compare(T o1, T o2)方法

TreeSet遍历

1.Iterator

//set是TreeSet的对象
for(Iterator iter = set.iterator(); iter.hasNext(); ) { 
    iter.next();
}  

2.for-each

//set为TreeSet的对象，且存的是String类型的元素
String[] arr = (String[])set.toArray(new String[0]);
for (String str:arr)
      System.out.printf("for each : %sn", str);
}