[数据结构与算法]集合的底层代码学习

集合分类

• 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 = {};//空数组
//调用无参构造方法时，默认不进行初始化。这里源码的注释并没有改还是初始化10
 public 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 code
      int 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;//如果第一次赋值就将它作为首节点
      else
          l.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.usrname.compareTo(this.usrname);
            if (eq==0)
            return Integer.compare(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().compareTo(user2.getUsrname());
         }else
            throw 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.75f
 public 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;
              //如果是TreeNode
          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);
                      //链上数据大于8是时调用treeifyBin(tab, hash);采用红黑树存储
                      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;
              }
          }
          //如果e!=null直接替换或添加
          if (e != null) { // existing mapping for key
              V 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 threshold
          newCap = oldThr;
      else {               // zero initial threshold signifies using defaults
          newCap = DEFAULT_INITIAL_CAPACITY;//首次调用回进到这static final int 
                   //DEFAULT_INITIAL_CAPACITY = 1 << 4 = 16
          newThr = (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=16
          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存储
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，此
时平均检索长度接近于常数。