集合的底层代码学习

底层代码学习"/>

集合的底层代码学习

集合分类

• Collection接口：单列数据，定义了存取一组对象的方法的集合
  • List：元素有序、可重复的集合
  • Set：元素无序、不可重复的集合

• Map接口：双列数据，保存具有映射关系“key-value对”的集合
  List接口
  数组具有局限性，通常用lList代替接口
  List类中元素有序、可重复，每个元素都有对应的索引
  List接口的实现类常用的有：ArrayList、LinkedList和Vector。
  |—ArrayList：List接口的主要实现类，使用transient Object[ ] elementData存储，频繁添加、查找推荐使用
  |—LinkedList:链式存储,使用双向链表实现，频繁的插入、删除效率比ArrayList高
  静态内部类：
  private static class Node {
  E item;
  Node next;
  Node prev;

   Node(Node<E> prev, E element, Node<E> next) {this.item = element;this.next = next;this.prev = prev;}
  

  }
  删除：将待删除元素的前置节点给它后面节点的前置节点，将它后置节点给它的前面元素的后置节点。插入类似。
  |—Vector:比List接口出现早(1.0)，效率低。
  ArrayList源码分析
  JDK7:
  ArrayList arrayList=new ArrayList();创建了一个长度为10的数组；
  arraylist.add()扩容：容量不够时，默认扩容为原来容量的1.5倍，并将原有数组中。
  不推荐使用空参构造器。
  JDK8:
  ArrayList arrayList=new ArrayList();

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//空数组
//调用无参构造方法时，默认不进行初始化。这里源码的注释并没有改还是初始化10public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

只有当调用add方法后才会创建长度为10的数组，并将数据add进去。类似于懒汉式，创建时间推迟,节省内存。
add方法

public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!! 先确定容量够不够elementData[size++] = e;return true;}private void ensureCapacityInternal(int minCapacity) {
//如果为空就给容量10或者minCapacity(size+1)if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}
//否则调用下面方法ensureExplicitCapacity(minCapacity);}private void ensureExplicitCapacity(int minCapacity) {modCount++;//验证线程是否安全// overflow-conscious code//如果当前实际长度大于当前容量if (minCapacity - elementData.length > 0)//扩容方法grow(minCapacity);}private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;//原容量int newCapacity = oldCapacity + (oldCapacity >> 1);//新容量1.5倍//如果新容量任然小于minCapacity，那就用minCapacity作为新容量if (newCapacity - minCapacity < 0)newCapacity = minCapacity;//private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - // 8;如果新容量溢出了调用 hugeCapacity(minCapacity);if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// minCapacity is usually close to size, so this is a win://最后将原来元素copy到现在的新数组中elementData = Arrays.copyOf(elementData, newCapacity);}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底层源码分析

//无参时调用空参构造器
public LinkedList() {}//参数为集合，任然时调用空参构造器，之后调用addAll(c)进行添加public LinkedList(Collection<? extends E> c) {this();addAll(c);}
/**
*调用add进行添加
*/
public boolean addAll(Collection<? extends E> c) {boolean modified = false;for (E e : c)if (add(e))modified = true;return modified;}

add方法

 public boolean add(E e) {linkLast(e);//调用方法添加元素return true;}
/**
*尾结点
*/
void linkLast(E e) {final Node<E> l = last;  //初始时transient Node<E> last;final Node<E> newNode = new Node<>(l, e, null);//为当前数据创建一个节点last = newNode;//last重新赋值if (l == null)first = newNode;//如果第一次赋值就将它作为首节点elsel.next = newNode;//否则将当前节点设置为尾结点size++;modCount++;}

Set接口、
|----------HashSet:线程不安全；可以存储null值

• LinkHashSet:HashSet子类，底层使用map
  |----------TreeSet:数据同类型，红黑树存储
  Set特点
  无序:存储的数据的存放顺序不是按照索引顺序添加，根据数据的hash值计算确定。
  不可重复：
  Set底层使用数组，jdk7中初始化为16，jdk8中在调用add才会初始化
  为了保证数据不重复，便需要进行数据比较，如果一个一个比较，当数据很多时，效率就会慢。 于是就有了hashcode，添加数据是首先会根据添加数据的hashcode值用算法求得该数据的索引，如果索引位置没有数据直接存入数组。当添加的数据位置上已经有元素时，会比较hashcode值。如果hashcode相同则用equals判断是否相同，如果相同那么两个数据就是相同的。
  若hashcode不同则使用链表将数据添加进去，这时同一个索引就存了多个数据。jdk7,8的插入方式不同。
  jdk7头插法：当前插入的数据放在数组中当头结点，之前的数据放在它后面。
  jdk8尾插法:添加的数据都往后放作为尾结点。
  这种添加方式在数据较多时优势明显，它首先会通过hash值计算存储位置，如果位置上有元素，就进入链表比较再添加，时间复杂度大大降低。
  因此向set中添加数据一定要重写equals()与hashcode()
  因为底层使用map, Set的扩容放在下面一起讨论
  TreeSet
  两种排序方式
  1.自然排序

 public void testSet(){TreeSet treeSet1=new TreeSet();treeSet1.add("lis");treeSet1.add("ons");treeSet1.add("las");System.out.println(treeSet1);System.out.println("----------------");//User类实现了Compleable接口/*public int compareTo(Object o) {if(o instanceof User){User user= (User) o;int eq=user.usrnamepareTo(this.usrname);if (eq==0)return Integerpare(user.age, this.age);else return eq;}else {throw new RuntimeException("数据类型不匹配");}}*/TreeSet treeSet2=new TreeSet();treeSet2.add(new User("lisi", 18));treeSet2.add(new User("suli", 20));treeSet2.add(new User("liufang", 19));treeSet2.add(new User("mumian", 17));treeSet2.add(new User("mumian", 18));System.out.println(treeSet2);}结果：[las, lis, ons]
----------------
[User{usrname='suli', age=20}, User{usrname='mumian', age=18}, 
User{usrname='mumian', age=17}, User{usrname='liufang', age=19}, 
User{usrname='lisi', age=18}]

定制排序

 public void testCo(){Comparator comparator= (o1, o2) -> {if(o1 instanceof User &&o2 instanceof User){User user1= (User) o1;User user2= (User) o2;return user1.getUsrname()pareTo(user2.getUsrname());}elsethrow new RuntimeException("输入数据类型不匹配");};TreeSet treeSet2=new TreeSet(comparator);treeSet2.add(new User("lisi", 18));treeSet2.add(new User("suli", 20));treeSet2.add(new User("liufang", 19));treeSet2.add(new User("mumian", 17));treeSet2.add(new User("mumian", 18));System.out.println(treeSet2);}
结果：
[User{usrname='lisi', age=18}, User{usrname='liufang', age=19}, 
User{usrname='mumian', age=17}, User{usrname='suli', age=20}]

Map接口(1.2)

• HashMap(1.2):线程不安全，效率高，key-value可以存null
  • LinkedHashMap(1.4)：频繁遍历操作适合
• TreeMap：排序，底层使用红黑树
• Hashtable(1.0):线程安全，线程不安全，不能存null
  • propeties：处理配置文件
    HashMap底层结构：
    1.7及之前：数组+链表
    1.8之后：数组+链表+红黑树
    key-value键值对
    key:不可重复，无序,用set存储
    value:可重复，无序可重复Collection存储。
    一个key-value封装成一个Entry对象，不可重复，无序用set存储。
    HashMap底层实现原理
    jdk1.7:
    HashMap hashMap=new HashMap();
    实例化后创建长度为16的一维数组Entry[] table
    map.put(key,value)
    调用key所在类的hashcode()计算key的hash值，经过算法处理得到其在Entry数组中的位置。

		如果位置上没有数据直接插入；如果位置上有数据比较哈希值，如果哈希值不同直接添加如果位置上哈希值相同，调用equals()方法比较：如果不同false添加成功如果返回true 就替换掉key对应的value

扩容时默认为原来的两倍，扩容条件：长度大于等于临界值且当前存放位置不为空。
jdk1.8:
HashMap hashMap=new HashMap();不进行初始化容量，懒加载
存放的数组是Node[ ],而不是Entry[ ]本质没有区别
当数组中某个链表形式存储的数据>8且数组长度>64时，使用红黑树存储，否则就扩容

//初始化容量16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
//加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//树化临界值
static final int TREEIFY_THRESHOLD = 8;
//不树化临界值，当树内部数量小于6时转化为链表
static final int UNTREEIFY_THRESHOLD = 6;
//最小树化容量
static final int MIN_TREEIFY_CAPACITY = 64;//static final float DEFAULT_LOAD_FACTOR = 0.75f;，默认加载因子0.75fpublic HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}//带有初始容量public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);//调用public HashMap(int initialCapacity, float loadFactor)}public HashMap(int initialCapacity, float loadFactor) {
//如果初始容量小于0，抛出异常if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);//如果自定义容量大于static final int MAXIMUM_CAPACITY = 1 << 30; 2^30将 
//  MAXIMUM_CAPACITY设为最大容量                                          if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;//如果加载因子<0或者不是float数据，抛出异常/*public static boolean isNaN(float v) {return (v != v);}
*/       if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;//临界值initialCapacity*loadFactor,当长度大于threshold时进行扩容。this.threshold = tableSizeFor(initialCapacity);}

扩容：

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) {Node<K,V>[] tab; Node<K,V> p; int n, i;//首次调用初始化resize()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;//如果hash相同且equals也相同if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;//如果是TreeNodeelse 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);//链上数据大于8是时调用treeifyBin(tab, hash);采用红黑树存储if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}//与上面相同属于替换的逻辑if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}//如果e!=null直接替换或添加if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;}
/**
*红黑树存储
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;//static final int MIN_TREEIFY_CAPACITY = 64//当数组长度小于64的时候进行扩容，而不是改成树结构if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)resize();//大于64时使用树else if ((e = tab[index = (n - 1) & hash]) != null) {TreeNode<K,V> hd = null, tl = null;do {TreeNode<K,V> p = replacementTreeNode(e, null);if (tl == null)hd = p;else {p.prev = tl;tl.next = p;}tl = p;} while ((e = e.next) != null);if ((tab[index] = hd) != null)hd.treeify(tab);}}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 thresholdnewCap = oldThr;else {               // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;//首次调用回进到这static final int //DEFAULT_INITIAL_CAPACITY = 1 << 4 = 16newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//0.75*16}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"})//造数组大小为newCap=16Node<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 orderNode<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;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.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存储
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);}}
**加载因子**
① 如果空间利用率高，那么经过的哈希算法计算存储位置的时候，会发现很多存储位置已经有数据了（哈希冲突）；
② 如果为了避免发生哈希冲突，增大数组容量，就会导致空间利用率不高。
而加载因子就是表示Hash表中元素的填满程度。加载因子 = 填入表中的元素个数 / 散列表的长度
加载因子越大，填满的元素越多，空间利用率越高，但发生冲突的机会变大了；加载因子越小，填满的元素越少，冲突发生的机会减小，但空间浪费了更多了，而且还会提高扩容rehash操作的次数。冲突的机会越大，说明需要查找的数据还需要通过另一个途径查找，这样查找的成本就越高。因此，必须在“冲突的机会”与“空间利用率”之间，寻找一种平衡与折衷。
**负载因子值的大小，对HashMap有什么影响**
1.负载因子的大小决定了HashMap的数据密度。
2.负载因子越大密度越大，发生碰撞的几率越高，数组中的链表越容易长,
造成查询或插入时的比较次数增多，性能会下降。
3.负载因子越小，就越容易触发扩容，数据密度也越小，意味着发生碰撞的
几率越小，数组中的链表也就越短，查询和插入时比较的次数也越小，性
能会更高。但是会浪费一定的内容空间。而且经常扩容也会影响性能，建
议初始化预设大一点的空间。
4. 按照其他语言的参考及研究经验，会考虑将负载因子设置为0.7~0.75，此
时平均检索长度接近于常数。HashMap不能保证元素的顺序,HashMap能够将键设为null，也可以将值设为null。与之对应的是Hashtable,(注意大小写：不是HashTable)，Hashtable不能将键和值设为null，否则运行时会报空指针异常错误；HashMap线程不安全，Hashtable线程安全