java-note[0]-JAVA源码-基本类型

String & StringBuffer & StringBuilder

String

/**
 * 使用 char 数组作为数据存储（在jdk1.9改用byte[]。优化存储空间占用，一个char占用两个byte空间）
 * 使用 final 修饰，说明value[]不可变。
 */ 
private final char value[];

/** 
 * 如果是通过构造函数创建字符串类型，那么值是通过传入的魔法值进行获取的，也就是说当前实例的value是常量池的引用。
 * 所以说 使用 `new String("123")` 这种方式会产生两个字符串，一个在常量池中，一个在堆里。
 */  
public String() {
    this.value = "".value;
}

public String(String original) {
    this.value = original.value;
    this.hash = original.hash;
}

StringBuffer

继承父类 AbstractStringBuilder value 与 String 不同，是没有被 final 修饰的。所以在连续拼接时，不会像 String 那样需要创建新的对象。在效率上更高。（效率提升来自于省略了对象实例化过程）

初始 capacity = 16

@Override
public StringBuilder append(String str) {
    super.append(str);
    return this;
}

char[] value;

public AbstractStringBuilder append(String str) {
    if (str == null)
        return appendNull();
    int len = str.length();
    ensureCapacityInternal(count + len);
    str.getChars(0, len, value, count);
    count += len;
    return this;
}

@Override
public String toString() {
    // Create a copy, don't share the array
    return new String(value, 0, count);
}

StringBuilder

相对于StringBuilder，他的一系列方法都使用 synchronized 进行加锁控制。
使用 toStringCache 作为 toString 方法的缓存器

private transient char[] toStringCache;

@Override
public synchronized StringBuffer append(String str) {
    toStringCache = null;
    super.append(str);
    return this;
}

/**
 * 没被修改的时候, 就可以直接把toStringCache作为new String的参数. 然后把这个String返回就行了。
 * 也就是cache有效的时候, 就不必进行arraycopy的复制操作. cache失效了才进行arraycopy的复制操作。
 */
@Override
public synchronized String toString() {
    if (toStringCache == null) {
        toStringCache = Arrays.copyOfRange(value, 0, count);
    }
    return new String(toStringCache, true);
}

Collection

java基本集合框架

List

ArrayList

/**
 * DEFAULT_CAPACITY 为默认容量，但是在初始化时使用 EMPTY_ELEMENTDATA 或者 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 进行初始化，
 * 所以此时真实容量大小为空（empty）
 */
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
    }
}

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/**
 * 添加
 */ 
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

/**
 * 当 elementData 为空时 比较 minCapacity 和 DEFAULT_CAPACITY 的值，取最大的。
 * 也就是， 有值的时候最小容量为 DEFAULT_CAPACITY = 10
 */ 
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

// 初始化 初始化容器
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // minCapacity (所需的容积大小) 大于 现在的容积大小时进行扩容。
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
// 扩容
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量=老容量+老容量的一半
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果所需的容量大于 MAX_ARRAY_SIZE (VM 限制的 大小 `MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8`)
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

/** 
 * 巨型容量扩容
 * 初始化为 Integer.MAX_VALUE
 */ 
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

LinkedList

1	public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList 实现了 List 和 Deque 接口，所以可以作为列表和双端队列使用。

transient int size = 0;
transient Node<E> first;
transient Node<E> last;

/**
* 静态内部 node 类
* 双向链表节点
*/
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;
    }
}

/**
* 获取 元素
* 如果 index 值小于链表长度 size 的一半，从头开始查询，否则从尾开始查询
*/
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

Node<E> node(int index) {
    // assert isElementIndex(index);
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}
/**
* 插入 元素
* 先查找再替换，并返回旧值
*/
public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

Vector

与 ArrayList 相似，但是 Vector 是同步的(它的public方法都使用了 synchronized 修饰)。所以说 Vector 是线程安全的动态数组。它的操作与 ArrayList 几乎一样。

Stack

/**
 * Stack 继承了 Vector 实现一个后进先出的堆栈。
 * 它的 pop() 和 peek() 方法也使用了 synchronized 修饰
 * push() 调用父级 Vector 的 addElement 方法 也是同步的
 */ 
public class Stack<E> extends Vector<E> {...}

Iterator 接口 & ListIterator 接口

Iterator 是一个接口，它是集合的迭代器。集合可以通过 Iterator 去遍历集合中的元素。

// 判断集合里是否存在下一个元素。如果有，hasNext() 方法返回 true
boolean hasNext();
// 返回集合里下一个元素
E next();
// 删除集合里上一次next方法返回的元素
void remove();
// 循环遍历（since 1.8）
void forEachRemaining(Consumer<? super E> action);

ListIterator 接口继承 Iterator 接口，提供了专门操作 List 的方法。

// 判断集合里是否存在上一个元素。如果有，hasPrevious() 方法返回 true
boolean hasPrevious();
// 返回上一个元素
E previous();

void set(E e);

void add(E e);

以上两个接口相比较会发现，ListIterator 增加了向前迭代的功能（ Iterator 只能向后迭代），ListIterator 还可以通过 add() 方法向 List 集合中添加元素（Iterator 只能删除元素）。

Queue

LinkedList

如上

ArrayDeque

// 底层是Object数组
transient Object[] elements;

private static final int MIN_INITIAL_CAPACITY = 8;

/**
 * 默认初始大小为16
 * 在如果是指定的大小，会通过 calculateSize(int numElements) 方法转换为对应的 2 的次方加1
 */
public ArrayDeque() {
    elements = new Object[16];
}

public ArrayDeque(int numElements) {
    allocateElements(numElements);
}

private void allocateElements(int numElements) {
    elements = new Object[calculateSize(numElements)];
}

private static int calculateSize(int numElements) {
    int initialCapacity = MIN_INITIAL_CAPACITY;
    // Find the best power of two to hold elements.
    // Tests "<=" because arrays aren't kept full.
    if (numElements >= initialCapacity) {
        initialCapacity = numElements;
        initialCapacity |= (initialCapacity >>>  1);
        initialCapacity |= (initialCapacity >>>  2);
        initialCapacity |= (initialCapacity >>>  4);
        initialCapacity |= (initialCapacity >>>  8);
        initialCapacity |= (initialCapacity >>> 16);
        initialCapacity++; // +1
        // 如果元素太大超过了 integer 的最大值 则会变成负数
        if (initialCapacity < 0)   // Too many elements, must back off
            initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
    }
    return initialCapacity;
}

PriorityQueue

优先队列PriorityQueue是Queue接口的实现，可以对其中元素进行排序，可以放基本数据类型的包装类（如：Integer，Long等）或自定义的类对于基本数据类型的包装器类，优先队列中元素默认排列顺序是升序排列但对于自己定义的类来说，需要自己定义比较器（Comparator）。

Set

HashSet

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable{
    // 底层使用HashMap存储数据，数据存在key部分，HashMap的value部分使用PRESENT填充
    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<>();
    }

    public HashSet(Collection<? extends E> c) {
        // 传入集合的size/负载因子+1，如果小于16 则初始化为16。
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }

    /**
     * 带 dummy 的构造函数是实例化一个LinkedHashMap作为底层数据存储，主要是实现LinkedHashSet
     * dummy只是为了区分构造函数，没有实际意义
     */ 
    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }
}

TreeSet & SortedSet

reeSet时SortedSet接口的实现类，TreeSet可以保证元素处于排序状态，它采用红黑树的数据结构来存储集合元素。
TreeSet支持两种排序方法：自然排序和定制排序，默认采用自然排序。

1 2	// NavigableMap接口继承了SortedMap private transient NavigableMap<E,Object> m;

Map

HashMap

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    // 默认最小容量
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;
    /**
     * 负载因子
     * 表示Hsah表中元素的填满的程度.若:加载因子越大,填满的元素越多,好处是,空间利用率高了,但:冲突的机会加大了.反之,加载因子越小,填满的元素越少,好处是:冲突的机会减小了,但:空间浪费多了.
     * 冲突的机会越大,则查找的成本越高.反之,查找的成本越小.因而,查找时间就越小. 
     * 因此,必须在 "冲突的机会"与"空间利用率"之间寻找一种平衡与折衷. 这种平衡与折衷本质上是数据结构中有名的"时-空"矛盾的平衡与折衷.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 链表转树结构的阈值
    static final int TREEIFY_THRESHOLD = 8;
    // 树转链表的阈值
    static final int UNTREEIFY_THRESHOLD = 6;
    // 最小树容量
    static final int MIN_TREEIFY_CAPACITY = 64;
    // 下一个要调整大小的大小值（容量*负载系数）
    int threshold;
}
/**
 * 静态内部类，链表节点的数据结构。
 */
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next; // 单向链表

    /**
     * Node 重写了hash算法以及equals方法
     * 注意！这里是Node内部类的hash，不是指HashMap的hash方法
     * Objects.hashCode(o) 的实现是如果o==null则返回0，否则调用o自身的hashCode()方法的返回值
     * hashCode与equals的重写绝大多数是同时的，因为约定：
     * equals相同则hash值相同，hash相同不一定equals。此处主要是因为前半部分约定。
     */
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

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

/**
 * HashMap的hash算法
 * 关于 hash算法的知识补充：
 * https://www.cnblogs.com/zxporz/p/11204233.html
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

/**
 * 这里可以看出，get()和containsKey()方法都是通过调用getNode()方法来获取或判断key的存在的。
 * 所以平时使用时这种：
 * if(map.containsKey(key)){
 *    map.get(key);
 * }
 * 这种代码实际上是要两次getNode()的，所以建议取值时还是不用通过和containsKey()方法判断了。
 * 如果是要做有就get没有就put的话可以先get再判断是否为空，如果是则put的形式。
 * 
 */
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first; 
        if ((e = first.next) != null) {
            // 如果头节点是TreeNode则使用红黑树的便利方式，否则用链表便利
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}

// map实例的isEmpty方法只是判断size是不是等于0，在平时使用时还要考虑map==null的情况防止空指针异常。
public boolean isEmpty() {
    return size == 0;
}

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

/**
 * Implements Map.put and related methods.
 *
 * @param hash
 * @param key
 * @param value 
 * @param onlyIfAbsent 如果为true，不会覆盖已有值
 * @param evict if false, the table is in creation mode.
 * @return 返回旧值或者null
 *
 * // 以下是允许LinkedHashMap后处理的回调空实现
 * // Callbacks to allow LinkedHashMap post-actions
 * void afterNodeAccess(Node<K,V> p) { }
 * void afterNodeInsertion(boolean evict) { }
 * void afterNodeRemoval(Node<K,V> p) { }
 */
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);
                    // 如果链长（binCount）大于 TREEIFY_THRESHOLD - 1 则转为红黑树
                    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;
    // 如果size大于下一个扩容点则扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

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

/**
 * 红黑树
 * 输入树箱。扩展LinkedHashMap.Entry（反过来扩展Node），因此可以用作常规节点或链接节点的扩展。
 * 红黑树算法：
 * https://segmentfault.com/a/1190000012728513
 */
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;
}

LinkedHashMap

/**
 * 
 */
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>{
    /**
     * 双向链表维护key的顺序。
     */
    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);
        }
    }
}

transient LinkedHashMap.Entry<K,V> head;
transient LinkedHashMap.Entry<K,V> tail;

/**
 * The iteration ordering method for this linked hash map: <tt>true</tt>
 * for access-order, <tt>false</tt> for insertion-order.
 * true 表示访问顺序 false表示插入顺序
 * 访问顺序是在调用get()put()等操作时会把该元素移到链表末尾，以此可以实现LRU算法。
 * @serial
 */
final boolean accessOrder;

HashTable

数据结构与HashMap一致，所有公共方法都使用synchronized修饰。但它是一个被抛弃的类，它的hash算法以及链表的结构没有像JDK1.8的HashMap那样优化。

TreeMap

/**
 * 看到NavigableMap就应该知道，TreeMap是一个自排序的集合map对象。 
 */
public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable{
  // 通过制定 Comparator 自定义排序规则否则默认使用元素类型的compareTo()方法进行排序。
  private final Comparator<? super K> comparator;
}

文章目录

String & StringBuffer & StringBuilder

Collection

List

ArrayList

LinkedList

Vector

Stack

Iterator 接口 & ListIterator 接口

Queue

LinkedList

ArrayDeque

PriorityQueue

Set

HashSet

TreeSet & SortedSet

Map

HashMap

LinkedHashMap

HashTable

TreeMap