Java集合类

集合类主要包括List,Set,Map,Queue,类图如下:

Map

HashMap:它根据键的hashCode值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null,允许多条记录的值为null。HashMap非线程安全,即任一时刻可以有多个线程同时写HashMap,可能会导致数据的不一致。如果需要满足线程安全,可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力,或者使用ConcurrentHashMap。 JDK1.8中的结构为哈希桶数组(Node[] table)+链表+红黑树(采用链地址法解决hash冲突,红黑树减少拉链长度)

Node节点的实现为:

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;
        }

        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;
        }
    }

红黑树转换时会将node转化为TreeNode

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }
//省略部分代码。。
}

 /**
     * HashMap.Node subclass for normal LinkedHashMap entries.
     */
    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }
// 所能容纳的key-value对极限  threshold = length(数组的长度,默认16) * Load factor
//超过threshold需要扩容,默认length为原来的两倍,length为2的n次方,主要是为了在取模和扩容时做优
//化,同时为了减少冲突,HashMap定位哈希桶索引位置时,也加入了高位参与运算的过程
  int threshold;             
     final float loadFactor;    // 负载因子,默认0.75
     int modCount;  //HashMap内部结构发生变化的次数,主要用于迭代的快速失败
     int size;  //所有node的数量

Hash算法:

static final int hash(Object key) {   //jdk1.8 & jdk1.7
     int h;
     // h = key.hashCode() 为第一步 取hashCode值
     // h ^ (h >>> 16)  为第二步 高位参与运算
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

确定Node在数组中索引位置:

static int indexFor(int h, int length) {  //jdk1.7的源码,jdk1.8没有这个方法,但是实现原理一样的
     return h & (length-1);  //第三步 取模,当length总是2的n次方时,h& (length-1)运算等价于对length取模
}

put方法:

扩容机制: JDK1.7:头插法,多线程下会导致死循环

 void resize(int newCapacity) {   //传入新的容量
     Entry[] oldTable = table;    //引用扩容前的Entry数组
     int oldCapacity = oldTable.length;         
     if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了
        threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1),这样以后就不会扩容了
        return;
    }
  
    Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组
     transfer(newTable);                         //!!将数据转移到新的Entry数组里
     table = newTable;                           //HashMap的table属性引用新的Entry数组
     threshold = (int)(newCapacity * loadFactor);//修改阈值
 }

void transfer(Entry[] newTable) {
     Entry[] src = table;                   //src引用了旧的Entry数组
      int newCapacity = newTable.length;
      for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
          Entry<K,V> e = src[j];             //取得旧Entry数组的每个元素
         if (e != null) {
            src[j] = null;//释放旧Entry数组的对象引用(for循环后,旧的Entry数组不再引用任何对象)
              do {
                 Entry<K,V> next = e.next;
                 int i = indexFor(e.hash, newCapacity); //!!重新计算每个元素在数组中的位置
                 e.next = newTable[i]; //标记[1]   头插法,将原来的数组位置节点放在e的next位置
                 newTable[i] = e;      //将元素放在数组上
                 e = next;             //访问下一个Entry链上的元素
             } while (e != null);
         }
     }
 }

JDK1.8:扩容是将capacity *2,确定数组下标的方法为 length -1 & hash值,就相当于链表中的节点可能还在原位置i,或者处于 i+ oldCapacity的位置。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有值,会更改hiTail对应Node的next的引用,从而做到顺序调整节点
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;  //如果hiTail有值,会更改hiTail对应Node的next的引用,从而做到顺序调整节点
                                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;
    }

Hashtable:Hashtable是遗留类,很多映射的常用功能与HashMap类似,不同的是它承自Dictionary类,并且是线程安全的,通过synchronized实现,任一时间只有一个线程能写Hashtable,并发性不如ConcurrentHashMap,因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用,不需要线程安全的场合可以用HashMap替换,需要线程安全的场合可以用ConcurrentHashMap替换。 Entry实现:

/**
     * Hashtable bucket collision list entry
     */
    private static class Entry<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Entry<K,V> next;

        protected Entry(int hash, K key, V value, Entry<K,V> next) {
            this.hash = hash;
            this.key =  key;
            this.value = value;
            this.next = next;
        }

        @SuppressWarnings("unchecked")
        protected Object clone() {
            return new Entry<>(hash, key, value,
                                  (next==null ? null : (Entry<K,V>) next.clone()));
        }

        // Map.Entry Ops

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        public V setValue(V value) {
            if (value == null)
                throw new NullPointerException();

            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 (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
               (value==null ? e.getValue()==null : value.equals(e.getValue()));
        }

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

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

LinkedHashMap:LinkedHashMap是HashMap的一个子类,保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的,也可以在构造时带参数,按照访问次序排序。

/**
     * HashMap.Node subclass for normal LinkedHashMap entries.
     */
    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

TreeMap :使用红黑树实现,TreeMap实现SortedMap接口,能够把它保存的记录根据键排序,默认是按键值的升序排序,也可以指定排序的比较器,当用Iterator遍历TreeMap时,得到的记录是排过序的。如果使用排序的映射,建议使用TreeMap。在使用TreeMap时,key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator,否则会在运行时抛出java.lang.ClassCastException类型的异常。

 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;
//省略部分代码
}

List

List集合代表一个元素有序,可重复的集合,集合中每个元素都有其对应的顺序索引。 ListIterator:可以向前迭代,而iterator只能够向后迭代。而且listIterator提供了add()的方法向List集合中添加元素,iterator只能够删除元素。 ArrayListVector类都是基于数组实现的List类,所以ArrayList和Vector类封装了一个动态的,允许再分配的Object[]数组。ArrayList或Vector对象使用initialCapaciy参数来设置该数组的长度,当向ArrayList或Vector中添加元素超出了该数组的长度时,他们的initialCapaciy会自动增长。 除此之外,两者的显著特征是ArrayList是线程不安全,Vector是线程安全的。为了使List变成线程安全的,可以使用Collections的工具类,不使用Vector,是因为过时了。 Vector还有个实现类Stack,实现元素能够像栈的操作进行,先进后出。 LinkedList:双链表实现,实现了List和Deque接口

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;
    transient Node<E> first;
    transient Node<E> last;
    public LinkedList() {
    }
//....
}

 private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
 public boolean add(E e) {
        linkLast(e);
        return true;
    }

Set Set集合与Collection基本相同,没有提供任何额外的方法。实际上Set就是Collection,只是行为略有不同。Set集合不允许包含相同的元素,如果试图把两个相同的元素加入同一个Set集合中,添加操作失败,add()方法返回false,且新元素不会被加入。 HashSet:HashMap实现

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable{
    private transient HashMap<E,Object> map;
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    /**
     * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
     * default initial capacity (16) and load factor (0.75).
     */
    public HashSet() {
        map = new HashMap<>();
    }

TreeSet:基于TreeMap实现

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
{
    /**
     * The backing map.
     */
    private transient NavigableMap<E,Object> m;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    /**
     * Constructs a set backed by the specified navigable map.
     */
    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }

    public TreeSet() {
        this(new TreeMap<E,Object>());
    }
}

Queue

队列接口,先入先出,定义了如下接口:

//IllegalStateException: if the element cannot be added at this  time due to capacity restrictions
boolean add(E e);
//if the element was added to this queue, else false
boolean offer(E e);
E remove();
 /**
     * Retrieves and removes the head of this queue.  This method differs
     * from {@link #poll poll} only in that it throws an exception if this
     * queue is empty.
     */
    E remove();

    /**
     * Retrieves and removes the head of this queue,
     * or returns {@code null} if this queue is empty.
     */
    E poll();

    /**
     * Retrieves, but does not remove, the head of this queue.  This method
     * differs from {@link #peek peek} only in that it throws an exception
     * if this queue is empty.
     */
    E element();

    /**
     * Retrieves, but does not remove, the head of this queue,
     * or returns {@code null} if this queue is empty.
     */
    E peek();

Deque 继承Queue接口,双端队列

void addFirst(E e);
void addLast(E e);
boolean offerFirst(E e);
boolean offerLast(E e);
E removeFirst(); 
E removeLast();
E pollFirst();
E pollLast();

    /**
     * Retrieves, but does not remove, the first element of this deque.
     * This method differs from {@link #peekFirst peekFirst} only in that it
     * throws an exception if this deque is empty.
*/
E getFirst();
 /**
     * Retrieves, but does not remove, the first element of this deque,
     * or returns {@code null} if this deque is empty.
     */
E peekFirst();
boolean offer(E e);
E poll();
//也有一些栈的接口......

PriorityQueue 最小堆来实现,并且使用index=0的数组

使用index = 0元素的数组的父子节点的下标关系:

  • k=父节点的index -> 左子节点的index = 2k + 1, 右子节点的index = (2 + 1)k
  • j = 子节点的index -> 父节点的index = (j -1) / 2 相对有序: 1、数组来实现二叉树,所以满足二叉树的特性。 2、根元素是最小的元素,父节点小于它的两个子节点。 3、树中的元素是相对有序的。
//插入元素时,插入到数组中的最后一个元素的后面,然后与该节点的父节点比较大小。如果插入的元素小于 
// 父节点元素,那么与父节点交换位置。然后插入元素交换到父节点位置时,又与该节点的父节点比较,直到 
// 大于父节点元素或者到达堆顶。该过程叫做上浮,即插入时上浮。
 public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        if (i == 0)
            queue[0] = e;
        else
            siftUp(i, e);
        return true;
    }

    private void siftUp(int k, E x) {
        if (comparator != null)
            siftUpUsingComparator(k, x);
        else
            siftUpComparable(k, x);
    }

  //插入时上升
    private void siftUpComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>) x;
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (key.compareTo((E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = key;
    }

//移除元素时,只能从堆顶移除元素,再取最后一个元素放到堆顶中。然后堆顶节点与子节点比较时,先取子 
// 节点中的较小者,如果堆顶节点大于较小子节点,那么交换位置。此时堆顶节点元素交换到较小子节点上。 
// 然后再与其较小子节点比较,直到小于较小子节点或者到达叶子节点为止。该过程叫做下沉,即移除元素时 
 // 下沉。
public E poll() {
        if (size == 0)
            return null;
        int s = --size;
        modCount++;
        E result = (E) queue[0];
        E x = (E) queue[s];
        queue[s] = null;
        if (s != 0)
            siftDown(0, x);
        return result;
    }

private void siftDown(int k, E x) {
        if (comparator != null)
            siftDownUsingComparator(k, x);
        else
            siftDownComparable(k, x);
    }

    //下沉

    private void siftDownComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>)x;
        int half = size >>> 1;        // loop while a non-leaf
        while (k < half) {
            int child = (k << 1) + 1; // assume left child is least
            Object c = queue[child];
            int right = child + 1;
            if (right < size &&
                ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
                c = queue[child = right];
            if (key.compareTo((E) c) <= 0)
                break;
            queue[k] = c;
            k = child;
        }
        queue[k] = key;
    }

最小堆问题的应用

ArrayDeque:数组实现

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable
{
    transient Object[] elements; // non-private to simplify nested class access

    transient int head;
    transient int tail;
    private static final int MIN_INITIAL_CAPACITY = 8;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • zookeeper源码分析(3)— 一次会话的创建过程

    在一次会话的创建过程中,需要客户端首先发送创建会话请求,服务端集群创建会话成功后会将响应发送给客户端。

    Monica2333
  • JUC学习笔记(二)—ConcurentHashMap

    Unsafe:是CAS的核心类,由于Java方法无法直接访问底层系统,需要通过本地(native)方法来访问,Unsafe相当于一个后门,基于该类可以直接操作特...

    Monica2333
  • zookeeper源码分析(2)-客户端启动流程

    客户端的入口,负责启动整个客户端。持有ClientCnxn和ZKWatchManager的实例,提供了客户端对节点操作的方法。

    Monica2333
  • [代码优化]null校验的优美处理

    我们写java代码的时候,使用对象前,都会下意识先判断对象非null,这是防止NPE的无奈之举,毕竟入门写代码时都写过npe的代码。这么做真的好吗,每层方法中都...

    逝兮诚
  • Netty 之 ChannelOutboundBuffer 源码分析

    每个 ChannelSocket 的 Unsafe 都有一个绑定的 ChannelOutboundBuffer , Netty 向站外输出数据的过程统一通过 C...

    java404
  • 使用Optional来减少null检查

    平常我们使用null检查在项目中简直太常见了,从数据库中查询到的数据可能不存在返回null,service中处理中发现不存在返回一个null,在互相调用的时候每...

    Dylan Liu
  • ThreadLocal从源码到应用

    最早接触到ThreadLocal是在阅读dianping的Cat-client,当时对它不是很理解,就搜索了一下,大概了解是一种解决线程安全问题的机制。现在再...

    用户1154259
  • 什么?字符串为空?

    当字符串为null,undefined,NaN,0,false,""这几个时,if(value)的结果都为false,if(!value)包含了我们常见的空值情...

    说故事的五公子
  • 将永久存储添加到Red Hat CDK Kit 3.0

    注意:本文介绍了在Red Hat容器开发工具包3.0测试版中使用的方法。在将来的版本中可能会有所变更。

    青橙.
  • 如何使用Java调用CM的API动态配置Yarn资源池

    用户在使用CDH集群大数据平台时会有需求在自己的统一管理平台上通过API接口能够动态的设置Yarn资源池,Cloudera Manager提供了丰富的API接口...

    Fayson

扫码关注云+社区

领取腾讯云代金券