十二、集合

本文主要是介绍十二、集合，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、集合的理解和好处

二、集合框架体系图

1. 集合主要是两组（单列集合、双列集合）
2. Collection 接口有两个重要的子接口 List、Set，他们的实现子类都是 单列集合
3. Map接口的实现子类 是 双列集合，存放的 k-v
   

三、Collection接口 特点 方法

3.1 Collection基本介绍

3.2 Collection接口常用方法

3.3 Collection接口遍历元素

3.3.1 方式1-使用Iterator(迭代器)

package com.collection_;import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;/*** @author Gao YongHao* @version 1.0*/
public class List01 {@SuppressWarnings({"all"})public static void main(String[] args) {Collection c = new ArrayList();c.add(new Book("三国演义", "罗贯中", 10.1));c.add(new Book("小李飞刀", "古龙", 5.1));c.add(new Book("红楼梦", "曹雪芹", 34.6));// 得到 c 对应的 迭代器Iterator iterator = c.iterator();for (; iterator.hasNext(); ) { // 判断是否还有数据Object next = iterator.next(); // 返回下一个元素，类型是ObjectSystem.out.println(next);}// 3.当退出while循环后，这时iterator迭代器，指向最后的元素// iterator.next(); // NoSuchElementException// 4. 如果需要重新遍历，需要重置迭代器iterator = c.iterator();}
}class Book {private String name;private String author;private double price;@Overridepublic String toString() {return "Book{" +"name='" + name + '\'' +", author='" + author + '\'' +", price=" + price +'}';}public String getName() {return name;}public void setName(String name) {this.name = name;}public String getAuthor() {return author;}public void setAuthor(String author) {this.author = author;}public double getPrice() {return price;}public void setPrice(double price) {this.price = price;}public Book(String name, String author, double price) {this.name = name;this.author = author;this.price = price;}
}

3.3.2 方式2-增强for循环

package com.collection_;import java.util.ArrayList;
import java.util.Collection;/*** @author Gao YongHao* @version 1.0*/
public class List02 {@SuppressWarnings({"all"})public static void main(String[] args) {Collection c = new ArrayList();c.add(new Book("三国演义", "罗贯中", 10.1));c.add(new Book("小李飞刀", "古龙", 5.1));c.add(new Book("红楼梦", "曹雪芹", 34.6));// 增强 for 也可以直接在数组使用// 解读// 1. 使用增强for，在Collection集合// 2. 增强for, 底层仍然是迭代器// 3. 增强for是可以理解成就是 简化版本的 迭代器遍历for (Object o : c) {System.out.println(o);}}
}

四、Collection接口的子接口：List 实现类：ArrayList、LinkedList、Vector

4.1 List接口基本介绍

package com.collection_;import java.util.ArrayList;
import java.util.List;/*** @author Gao YongHao* @version 1.0*/
public class List03 {@SuppressWarnings("all")public static void main(String[] args) {List list = new ArrayList();// 1. List集合类中元素有序（即添加顺序和去除顺序一致）、且可重复list.add("jack");list.add("tom");list.add("mary");list.add("tom");// 2. List集合中的每个元素都有其对应的顺序顺序索引，即支持索引System.out.println(list.get(0));}
}

4.2 List接口的方法

package com.collection_;import java.util.ArrayList;
import java.util.List;/*** @author Gao YongHao* @version 1.0*/
public class List04 {@SuppressWarnings("all")public static void main(String[] args) {List list = new ArrayList();for (int i = 0; i < 11; i++) {list.add("Hello" + i);}list.add(1, "韩顺平教育");System.out.println("第五个元素:" + list.get(4));list.remove(5); // 删除第6个元素list.set(6, "7"); // 修改第7个元素for (Object o : list) {System.out.println(o);}}
}

4.3 List的三种遍历方式

4.4 ArrayList底层结构和源码分析

package com.collection_;import java.util.ArrayList;/*** @author Gao YongHao* @version 1.0*/
@SuppressWarnings({"all"})
public class List06 {public static void main(String[] args) {/*源码：使用无参构造器。创建了一个空的 private static Object[] elementData={} (在堆中独一份)public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}*/ArrayList list = new ArrayList();/*源码：使用有参构造器。创建了一个指定大小为8的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);}}*/
//        ArrayList list = new ArrayList(8);// 使用for给list集合添加 1-10 数据for (int i = 1; i <= 10; i++) {/*            1. 先使用integer.valueOf方法将基本数据类型数据装箱为包装类2. add源码：(1) 先确定是否要扩容 ensureCapacityInternal(2) 然后再执行赋值操作public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!!elementData[size++] = e;return true;}3.     private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity); // a. 空数组第一次扩容量为10}return minCapacity; // b. 若为非空数组则拟定的最小容量为 size + 1}private void ensureExplicitCapacity(int minCapacity) {modCount++; // a. 记录当前elementData被修改的次数// overflow-conscious codeif (minCapacity - elementData.length > 0) // b. 判断所需的最小容量是否大于当前elementData数组的容量(如果elementData的大小不够，就调用 grow() 去扩容)grow(minCapacity);}private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length; // 原数组容量int newCapacity = oldCapacity + (oldCapacity >> 1); // 新数组容量 == 原数组容量 + 原数组容量/2 == 1.5 * 原数组容量（即：扩容1.5倍）if (newCapacity - minCapacity < 0) // 第一次扩容时，oldCapacity == 0，newCapacity == 0，minCapacity == 10。第二次以及以后，按照1.5倍扩容newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// minCapacity is usually close to size, so this is a win:// 将 elementData 的前 newCapacity 个数复制到新的数组对象中（newCapacity 若大于elementData 原来的元素个数，多出的部分被置为null）elementData = Arrays.copyOf(elementData, newCapacity);}*/list.add(i);}// 使用for给list集合添加 11-15 数据for (int i = 11; i <= 15; i++) {// 第二次扩容为1.5倍 10 --> 15list.add(i);}list.add(100); // 第三次扩容为1.5倍 15 --> 22list.add(200);list.add(null);}
}

4.5 Vector底层结构和源码剖析

// Vector 空参构造器public Vector() {this(10); // 直接初始一个容量为10的Object数组}
// vector的add方法public synchronized boolean add(E e) {modCount++;ensureCapacityHelper(elementCount + 1);elementData[elementCount++] = e;return true;}private void ensureCapacityHelper(int minCapacity) {// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;int newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity); // 默认capacityIncrement  == 0，即扩张2倍if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);elementData = Arrays.copyOf(elementData, newCapacity);}

4.6 Vector与ArrayList的比较

4.7 LinkedList底层结构

// 简单的双向链表演示
package com.collection_;/*** @author Gao YongHao* @version 1.0*/
public class LinkedList02 {public static void main(String[] args) {Node jack = new Node("jack");Node tom = new Node("tom");Node hsp = new Node("老韩");// 连接三个节点，形成双向链表// jack --> tom --> hspjack.setNext(tom);tom.setNext(hsp);// hsp --> tom --> jackhsp.setPre(tom);tom.setPre(jack);Node first = jack; // 双向链表的头结点Node last = hsp; // 双向链表的尾结点// 从头到尾遍历Node n = first;while (true) {if (n == null) break;System.out.println(n.getData());n = n.getNext();}// 从尾到头遍历n = last;while (true) {if (n == null) break;System.out.println(n.getData());n = n.getPre();}// 演示链表的添加对象/数据，是多么方便// 要求：是在 tom 与 hsp之间插入一个对象 smithNode smith = new Node("smith");tom.setNext(smith);smith.setPre(tom);smith.setNext(hsp);hsp.setPre(smith);// 从头到尾遍历n = first;while (true) {if (n == null) break;System.out.println(n.getData());n = n.getNext();}}
}class Node {private Node pre;private Node next;private Object data;public Node(Object data) {this.data = data;}public Node getPre() {return pre;}public void setPre(Node pre) {this.pre = pre;}public Node getNext() {return next;}public void setNext(Node next) {this.next = next;}public Object getData() {return data;}public void setData(Object data) {this.data = data;}public Node(Node pre, Node next, Object data) {this.pre = pre;this.next = next;this.data = data;}
}

// LinkedList底层讲解
package com.collection_;import java.util.LinkedList;/*** @author Gao YongHao* @version 1.0*/
@SuppressWarnings({"all"})
public class LinkedList03 {public static void main(String[] args) {// 源码阅读/** 1. LinkedList linkedList = new LinkedList();*       public LinkedList() {*       }* 2. 这时 linkedList 的属性 size = 0  first = null   last = null*** */LinkedList linkedList = new LinkedList();/* add()源码分析public boolean add(E e) {linkLast(e); // 在尾部新建结点，并更新size、first与last对象等return true;}* void linkLast(E e) {final Node<E> l = last;final Node<E> newNode = new Node<>(l, e, null); // 创建新节点并初始化prev与数据属性last = newNode; // 将链表的last指向新生成的节点if (l == null) // 如果原来的last为空，则表明原链表没有数据first = newNode; // 设置first也指向新生成的节点elsel.next = newNode; // 否则，原最后的结点的next指向新创建的结点对象size++;modCount++;}*** */linkedList.add(1);// 删除结点的方法(无参表示删除头结点信息)// 源码/* 1.* public E remove() {*    return removeFirst();* }** 2.* public E removeFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return unlinkFirst(f);}** 3. 执行 unlinkFirst , 将 f 指向的双向链表的第一个结点拿掉* private E unlinkFirst(Node<E> f) {// assert f == first && f != null;final E element = f.item; // 获取原头结点的数据final Node<E> next = f.next;f.item = null;f.next = null; // help GCfirst = next; // 设置first指向原头结点的下一个结点if (next == null) // 判断新的头结点是否存在last = null; // 不存在意味着链表没有元素,则设置last = nullelsenext.prev = null; // 存在则把新的头结点的prev设置为nullsize--;modCount++;return element; // 返回删除的头结点的数据}** */linkedList.remove();// 源码/* 1. checkElementIndex用于检查index的有效性* public E get(int index) {checkElementIndex(index);return node(index).item;}** 2. node: 对比index相对头尾哪个更近，从较近的一端开始遍历index个对象* 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;}}**** */linkedList.get(1);System.out.println("LinkedList=" + linkedList);}
}

4.8 ArrayList和LinkedList的比较

五、Collection接口的子接口：Set实现类：HashSet、LinkedHashSet

5.1 Set接口基本介绍

5.2 Set接口常用方法与遍历方式

public class SetMethod{public static void main(String[] args){// 1. 以 Set 接口的实现类 HaskSet 来讲解 Set 接口的方法// 2. set 接口的实现类的对象(Set 接口对象)，不能存放重复的元素,可以添加一个null值// 3. set 接口对象存放数据是无序，即添加的顺序与取出的顺序不一致// 4. 注意：取出的顺序虽然不是添加的顺序，但是他是固定的Set set = new HashSet();set.add("john");set.add("lucy");set.add("john"); // 重复set.add("jack");set.add("null");set.add("null"); // 再次添加null}
}

5.3 HashSet的全面说明

// 重复数据的处理机制
package com.collection_;import java.util.HashSet;/*** @author Gao YongHao* @version 1.0*/
@SuppressWarnings({"all"})
public class Set01 {public static void main(String[] args) {HashSet set = new HashSet();// 说明:// 1. 在指执行add方法后，会返回一个boolean值// 2. 如果添加成功，返回 true，否则返回 falseSystem.out.println(set.add("john")); // TSystem.out.println(set.add("lucy")); // TSystem.out.println(set.add("john")); // F,后添加的失败System.out.println(set.add("jack")); // TSystem.out.println(set.add("Rose")); // T// 3. 可以通过 remove 指定删除哪个对象set.remove("john");System.out.println("set=" + set);// set=[Rose, lucy, jack]set = new HashSet();set.add("lucy"); // 添加成功set.add("lucy"); // 加入不了set.add(new Dog("tom")); // 添加成功set.add(new Dog("tom")); // 添加成功System.out.println("set=" + set); // set=[Dog{name='tom'}, Dog{name='tom'}, lucy]// 看源码，做分析，待HashMap讲完后再看set.add(new String("hsp")); // 添加成功set.add(new String("hsp")); // 加入不了System.out.println("set=" + set); // set=[hsp, Dog{name='tom'}, Dog{name='tom'}, lucy]}
}class Dog { // 定义了一个Dog类private String name;public Dog(String name) {this.name = name;}@Overridepublic String toString() {return "Dog{" +"name='" + name + '\'' +'}';}
}

5.4 HashSet底层机制说明

// 简单实现HashSet底层
package com.collection_;/*** @author Gao YongHao* @version 1.0*/
public class HashSetStructure {public static void main(String[] args) {// 模拟一个HashSet的底层(HashMap的底层结构)// 1. 创建一个数组，数组的类型是 Node[]// 2. 有些人，直接把 Node[] 数组称为 表Node1[] table = new Node1[16];System.out.println("table=" + table);// 3.创建结点Node1 john = new Node1("john");table[2] = john;Node1 jack = new Node1("jack");john.next = jack; // 将 jack 结点挂载到 johnNode1 rose = new Node1("rose");jack.next = rose; // 将 rose 结点挂载到 jackNode1 lucy = new Node1("lucy");table[3] = lucy; // 把 lucy 放置于 table索引为3的存储空间System.out.println("table=" + table);}
}class Node1 { // 结点，存储数据，可以指向下一个结点，从而形成链表Object item; // 存放数据Node1 next; // 指向下一个结点@Overridepublic String toString() {return "Node1{" +"item=" + item +", next=" + next +'}';}public Node1(Object item) {this.item = item;}public Node1(Object item, Node1 next) {this.item = item;this.next = next;}
}

// HashSet底层实现
package com.collection_;import java.util.HashSet;/*** @author Gao YongHao* @version 1.0*/
@SuppressWarnings({"all"})
public class HashSet01 {public static void main(String[] args) {/** HashSet的源码解读* 1. 执行 HashSet()* public HashSet() {map = new HashMap<>();}** 2. 执行第一次 add() 方法* public boolean add(E e) { // PRESENT 为Object对象，起到占value位的作用*       返回null表示添加成功return map.put(e, PRESENT)==null;}** 3. 执行 put() 方法* public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}** 4. 执行 hash() 方法，得到Key对应的hash值* static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}*** 5. 执行 putVal() 方法* final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i; // 定义了辅助变量* table 就是 HashMap 的一个数组，类型是 Node[]* if 语句表示如果当前的table是空的或者大小为0* 就是第一次扩容,到16个空间if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;* (1) 根据key，得到的hash去计算该key应该存放到table表的哪个索引位置* 并且把这个位置的对象赋给辅助变量p* (2) 判断 p 是否为 null* (2.1) 如果p为null，表示原数组中没有元素则直接创建一个Node (key="java",value=PRESENT)* (2.2) 就放在该位置 tab[i] = new Node(hash,key,value,null)if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {* (3) 如果有则根据判断key值是否相同，相同则将value值作替换;不同则按红黑树或链表的方式计算其余node结点对象是否与传入的key相同(循环遍历),全部都没有则进行添加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);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 表示原链表、红黑树中存在的HashMap$Node对象// 若key相同则进行value替换（HashSet设置了value都指向同一对象，因此替换也是不改变HashMap$Node中value的指向）if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value; // 替换value值afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold) // 每加入一个结点（不管是在table中，还是在node链表中），size加1，大于 threshold 就扩容resize();afterNodeInsertion(evict);return null;}** */HashSet hashSet = new HashSet();hashSet.add("java");//第二次 add(由于php与java不同，直接添加)// add --> put --> putValhashSet.add("php");//第三次 add(由于"java"与"java"相同，添加失败)// add --> put --> putVal// add会返回原HashSet中的已有的包含"java"数据的对象/** final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;* 由于已经初始化table则不执行此if代码块if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;* 由于已经有 java 数据了，则执行else{...}* 此处p为之前的table中的保存java信息的node结点对象if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k; // 创建辅助变量* 判断是否与当前索引位置对应的链表的第一个元素重复：* 重复判断条件一：hash相同* 重复判断条件二：* （2.1）与保存的值==为true(指向同一个对象)*  或* （2.2）保存的值不为空且与保存的值 equals 方法为true（内容相同）* 若重复则不会添加该数据，并会将该数据内容指向的value值作替换并返回更新后的value值if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;** 在判断是不是一棵红黑树* 若是则调用 putTreeVal ，来进行添加else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else { // 是链表的情况* 若第一个结点中元素与拟添加的元素不重复，则依次与该空间位置上的* 链表元素比较是否重复* (1) 若检查完均不重复则将当前拟添加的结点接入链表尾部*   (1.1) !!!注意：在把元素添加到链表后，立即判断  该链表是否已经达到8个结点*   , 就调用 treeifyBin()  对当前的链表进行 "树化"(转成红黑树)*   (1.2) !!!注意，在转成红黑树时还进行一个判断,判断条件如下:*       if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)*           resize();*       如果上面条件成立，先对table扩容.*       如果上面条件不成立时，才进行转成红黑树* (2) 若其中有重复的结点则，将table中的结点返回for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);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;}}** 存在重复的值则返回table中原有的对象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) // 每加入一个结点（不管是在table中，还是在node链表中），size加1resize();afterNodeInsertion(evict);return null;}* */hashSet.add("java"); // 有重复元素,添加失败System.out.println("set=" + hashSet);}
}

package com.collection_;import java.util.HashSet;/*** @author Gao YongHao* @version 1.0*/
@SuppressWarnings({"all"})
public class HashSet02 {public static void main(String[] args) {HashSet hashSet = new HashSet();for (int i = 0; i < 100; i++) {// 源码// add() --> put() --> putVal()/** 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);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;}}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;if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)resize();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);}}*** */// 由于均是在链表上添加元素(hash相等但equals()还是Object继承下来的==)，// 每次添加一次均会查看链表元素个数是否已经大于等于8个(第一个树化条件)// 若满足条件则会进入 treeifyBin() 方法看是否满足另一树化条件:// 判断table数组长度是否大于等于64!!!// if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)//        resize();// 若满足则进行树化; 若不满足则进行扩容操作(注意此处没有判断元素个数是否大于threshold!)// capcity*=2   threshold*=2// 因此，在第8次添加时扩容 capcity:16(threshold=16*0.75=12) ---> capcity:32(threshold=32*0.75=24)// 在第9次添加时扩容 capcity:32(threshold=32*0.75=24) ---> capcity:64(threshold=64*0.75=48)// 在第10次添加时进行树化，不进行扩容!hashSet.add(i);}}
}class Human {private String name;@Overridepublic int hashCode() { // 自定义 hashCode 使每个 Human对象 的hashcode值相等return 100;}public Human(String name) {this.name = name;}
}

5.5 LinkedHashSet的全面说明

• 注：LinkedHashSet 是对 HashSet 的扩展，其在 HashSet 由 数组 + 单链表 + 红黑树 构成的前提下，额外维护了一个 双向链表 用于保存输入数据的存储顺序
  

package com.collection_;import java.util.LinkedHashSet;
import java.util.Objects;
import java.util.Set;/*** @author Gao YongHao* @version 1.0*/
@SuppressWarnings({"all"})
public class LinkedHashSet01 {public static void main(String[] args) {// 分析LinkedHashSet的底层机制Set set = new LinkedHashSet();// 解读// 1. LinkedHashSet 加入顺序和取出元素/数据顺序一致// 2. LinkedHashSet 底层维护的是一个 LinkedHashMap（是HashMap的子类）// 3. LinkedHashSet 底层结构（数组table+双向链表）// 4. 添加第一次时，直接将 数组table 扩容到16，存放的结点类型是 LinkedHashMap$Entry// 5. 数组是 HashMap$Node[] 存放的元素/数据是 LinkedHashMap$Entry(增加了双向链表的前后结点引用before, after)/*// 继承关系是在内部类完成的* 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);}}*6. add --> put --> putValfinal 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)// LinkedHashMap重写了newNode()方法，在创建一个Entry类型对象返回的同时构建了双向链表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);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;}}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;}7. newNode方法Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {LinkedHashMap.Entry<K,V> p =new LinkedHashMap.Entry<K,V>(hash, key, value, e);linkNodeLast(p); // 将p加入双向链表return p;}8. linkNodeLast方法private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {LinkedHashMap.Entry<K,V> last = tail;tail = p;if (last == null)head = p;else {p.before = last;last.after = p;}}* */set.add(new String("AA"));set.add(456);set.add(456);set.add(new Customer("刘", 1001));set.add(123);set.add("HSP");set.add(new Customer("张", 1002)); // 会根据HashMap的规则加入到单向链表中，同时也会被双向链表记录// 由双向链表从头结点开始遍历// [AA, 456, Customer{name='刘', no=1001}, 123, HSP, Customer{name='张', no=1002}]System.out.println(set);}
}class Customer {private String name;private int no;@Overridepublic String toString() {return "Customer{" +"name='" + name + '\'' +", no=" + no +'}';}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Customer customer = (Customer) o;return no == customer.no &&Objects.equals(name, customer.name);}@Overridepublic int hashCode() {return 100;}public Customer(String name, int no) {this.name = name;this.no = no;}
}

5.6 TreeSet

package com.collection_;import java.util.Comparator;
import java.util.TreeSet;/*** @author Gao YongHao* @version 1.0*/
@SuppressWarnings({"all"})
public class TreeSet_ {public static void main(String[] args) {//解读// 1. 当我们使用无参构造器，创建TreeSet时，仍然是无序的// 2. 希望添加的元素，按照字符串大小来排序// 3. 使用 TreeSet 提供的一个构造器，可以传入一个比较器（匿名内部类）//    并指定排序规则TreeSet treeSet = new TreeSet(new Comparator() {// 下面 调用String的 compareTo方法进行字符串大小比较@Overridepublic int compare(Object o1, Object o2) {return -((String) o1).compareTo(((String) o2));}});// 1. 构造器把传入的比较器对象，赋给了 TreeSet底层的 TreeMap的属性/** public TreeSet(Comparator<? super E> comparator) {this(new TreeMap<>(comparator));}** public TreeMap(Comparator<? super K> comparator) {this.comparator = comparator;}** 2. 在调用 add 方法时，实际调用的是TreeMap的put方法* public V put(K key, V value) {Entry<K,V> t = root; // t最开始是二叉树的根结点if (t == null) {compare(key, key); // type (and possibly null) checkroot = new Entry<>(key, value, null);size = 1;modCount++;return null;}int cmp;Entry<K,V> parent;// split comparator and comparable pathsComparator<? super K> cpr = comparator;if (cpr != null) { // cpr就是传入的匿名内部类(对象)do {parent = t;* 动态绑定到我们的匿名内部类的compare方法cmp = cpr.compare(key, t.key);if (cmp < 0)t = t.left; // 如果小于当前结点的值，向左边继续寻找（直至）左指向结点为null的(父)结点else if (cmp > 0)t = t.right; // 如果大于当前结点的值，向右边继续寻找（直至）右指向结点为null的(父)结点elsereturn t.setValue(value); // 与某一结点的key相同则替换原来的value值} while (t != null);}else { // 没有传入自定义的Comparable对象，* 则尝试使用key自己的compareTo方法进行比较if (key == null)throw new NullPointerException();@SuppressWarnings("unchecked")Comparable<? super K> k = (Comparable<? super K>) key;do {parent = t;cmp = k.compareTo(t.key);if (cmp < 0)t = t.left;else if (cmp > 0)t = t.right;elsereturn t.setValue(value);} while (t != null);}Entry<K,V> e = new Entry<>(key, value, parent);if (cmp < 0) // 最后一次判别若是小于，则parent指向一个左指向为null的结点对象parent.left = e; // 添加数结点到二叉树中else // 最后一次判别若是大于，则parent指向一个右指向为null的结点对象parent.right = e; // 添加数结点到二叉树中fixAfterInsertion(e);size++;modCount++;return null;}* */treeSet.add("jack");treeSet.add("tom");treeSet.add("sp");treeSet.add("a");System.out.println("treeSet=" + treeSet);}
}

六、Map接口 特点方法 遍历方式

6.1 Map接口实现类的特点

package com.collection_;import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;/*** @author Gao YongHao* @version 1.0*/
@SuppressWarnings({"all"})
public class MapSource_ {public static void main(String[] args) {Map map = new HashMap();map.put("no1", "韩顺平");//k-vmap.put("no2", "张无忌");//k-v// 解读// 1. k-v 最后是 HashMap$Node(实现了Map.Entry) node = newNode(hash,key,value,null)// 2. k-v 为了方便程序员的遍历，还会 创建 EntrySet 集合，该集合存放的元素类型是 Map.Entry,// 而一个 Map.Entry 对象就有k,v。EntrySet<Map.Entry<K,V>> 即：HashMap的属性 transient Set<Map.Entry<K,V>> entrySet;// 3. EntrySet中，定义类型是 Map.Entry，但是实际上存放的还是 HashMap&Node (多态)// 这是因为 HashMap$Node 实现了 Map.Entry// 4. 当把 HashMap$Node 对象 存放到 entrySet 中就方便我们的遍历，// 因为 Map.Entry 提供了重要的方法// k getKey(); V getValue();// entrySet()返回 EntrySet 对象(Set对象)// EntrySet对象内部并没有维护数据，只是实现了Iterator接口，// 并在next()返回了由HashMap维护的table中的HashMap$Node类型的数据(即：成员内部类调用外部类的成员属性)// 简单的说，EntrySet对象内部没有额外的变量来保存数据，它直接根据HashMap的table对数据进行操作(即：与HashMap同数据源)/** final class EntrySet extends AbstractSet<Map.Entry<K,V>> {public final int size()                 { return size; }public final void clear()               { HashMap.this.clear(); }*** 这里实现了Iterator接口的方法public final Iterator<Map.Entry<K,V>> iterator() {return new EntryIterator();}public final boolean contains(Object o) {if (!(o instanceof Map.Entry))return false;Map.Entry<?,?> e = (Map.Entry<?,?>) o;Object key = e.getKey();Node<K,V> candidate = getNode(hash(key), key);return candidate != null && candidate.equals(e);}public final boolean remove(Object o) {if (o instanceof Map.Entry) {Map.Entry<?,?> e = (Map.Entry<?,?>) o;Object key = e.getKey();Object value = e.getValue();return removeNode(hash(key), key, value, true, true) != null;}return false;}public final Spliterator<Map.Entry<K,V>> spliterator() {return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);}public final void forEach(Consumer<? super Map.Entry<K,V>> action) {Node<K,V>[] tab;if (action == null)throw new NullPointerException();if (size > 0 && (tab = table) != null) {int mc = modCount;for (int i = 0; i < tab.length; ++i) {for (Node<K,V> e = tab[i]; e != null; e = e.next)action.accept(e);}if (modCount != mc)throw new ConcurrentModificationException();}}}*** */// 可以理解为 EntrySet对象 的每一个元素都是 Map.Entry的子类HashMap$Node的对象，// 而该对象是在HashMap中的table中组织，EntrySet对象的元素仅是HashMap$Node的对象的引用Set set = map.entrySet();System.out.println(set.getClass());//HashMap$EntrySetfor (Object obj : set) {//System.out.println(obj.getClass()); // HashMap$Node// 为了从 HashMap$Node 取出k-v// 1. 先做一个向下转型Map.Entry entry = (Map.Entry) obj;System.out.println(entry.getKey() + "-" + entry.getValue());}// 单独获取所有key的set集合Set keys = map.keySet(); // 直接根据table返回由key组成的引用Set集合// 单独获取所有value的Collection集合Collection values = map.values(); // 直接根据table返回由value组成的引用Collection集合}
}

6.2 Map接口和常用方法

6.3 Map接口遍历方法

package com.collection_;import java.util.*;/*** @author Gao YongHao* @version 1.0*/
@SuppressWarnings({"all"})
public class HashSet03 {public static void main(String[] args) {Map map = new HashMap();map.put("邓超", "孙俪");map.put("王宝强", "马蓉");map.put("宋喆", "孙俪");map.put("刘令博", null);map.put(null, "刘亦菲");map.put("鹿晗", "关晓彤");// 第一种 keySetSet keys = map.keySet();// (1) 增强for循环for (Object obj : keys) {System.out.println(obj + "-" + map.get(obj));}// (2) iterator遍历Iterator iterator = keys.iterator();while (iterator.hasNext()) {Object k = iterator.next();System.out.println(k + "-" + map.get(k));}// 第二种只看 value 值Collection values = map.values();// (1) 增强for循环for (Object obj : values) {System.out.println(obj);}// (2) iterator遍历Iterator iterator1 = values.iterator();while (iterator1.hasNext()) {System.out.println(iterator1.next());}// 第三种 entrySetSet set = map.entrySet();// (1) 增强for循环for (Object obj : set) {Map.Entry e = (Map.Entry) obj; // obj运行类型是HashMap$NodeSystem.out.println(e.getKey() + "-" + e.getValue());}// (2) iterator遍历Iterator iterator2 = set.iterator();while (iterator2.hasNext()) {Map.Entry e = (Map.Entry) iterator2.next();System.out.println(e.getKey() + "-" + e.getValue());}}
}

6.4 HashMap小结

6.5 HashMap底层机制及剖析

• 源码与HashSet相同，参见HashSet的底层机制部分
  

6.6 HashTable的基本介绍

• 底层是：数组 + 单向链表
  

package com.collection_;import java.util.Hashtable;/*** @author Gao YongHao* @version 1.0*/
@SuppressWarnings({"all"})
public class HashTable01 {public static void main(String[] args) {// 解读// 1. 底层由数组 Hashtable$Entry[] 初始化大小为 11/** public Hashtable() {this(11, 0.75f);}* */// 2. 临界值 threshold 8 = 11 * 0.75Hashtable hashtable = new Hashtable();hashtable.put("john", 100);//ok/* 3. put方法key与value均不能为null!!!* public synchronized V put(K key, V value) {// Make sure the value is not null* value不能为nullif (value == null) {throw new NullPointerException();}// Makes sure the key is not already in the hashtable.Entry<?,?> tab[] = table;* key不能为null!!!int hash = key.hashCode();int index = (hash & 0x7FFFFFFF) % tab.length;@SuppressWarnings("unchecked")Entry<K,V> entry = (Entry<K,V>)tab[index];for(; entry != null ; entry = entry.next) {if ((entry.hash == hash) && entry.key.equals(key)) {V old = entry.value;entry.value = value; // 相同 key 替换 valuereturn old;}}addEntry(hash, key, value, index);return null;}** 4. addEntry方法。添加 k-v 封装至 Entryprivate void addEntry(int hash, K key, V value, int index) {modCount++;Entry<?,?> tab[] = table;if (count >= threshold) {// Rehash the table if the threshold is exceededrehash();tab = table;hash = key.hashCode();index = (hash & 0x7FFFFFFF) % tab.length;}// Creates the new entry.@SuppressWarnings("unchecked")Entry<K,V> e = (Entry<K,V>) tab[index];tab[index] = new Entry<>(hash, key, value, e);count++;}*4. 扩容机制 rehash()protected void rehash() {int oldCapacity = table.length;Entry<?,?>[] oldMap = table;// overflow-conscious code// 新容量为原容量的 2倍加1int newCapacity = (oldCapacity << 1) + 1;if (newCapacity - MAX_ARRAY_SIZE > 0) {if (oldCapacity == MAX_ARRAY_SIZE)// Keep running with MAX_ARRAY_SIZE bucketsreturn;newCapacity = MAX_ARRAY_SIZE;}Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];modCount++;threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);table = newMap;// 迁移数据for (int i = oldCapacity ; i-- > 0 ;) {for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {Entry<K,V> e = old;old = old.next;int index = (e.hash & 0x7FFFFFFF) % newCapacity;e.next = (Entry<K,V>)newMap[index];newMap[index] = e;}}}*/hashtable.put(null, 100);//异常hashtable.put("john", null);//异常hashtable.put("lucy", 100);//okhashtable.put("lic", 100);//okhashtable.put("lic", 88);//替换System.out.println(hashtable);}
}

6.7 HashTable 和 HashMap 对比

6.8 Properties类

文章：https://www.cnblogs.com/xudong-bupt/p/3758136.html

6.9 TreeMap

• 底层分析与TreeSet描述一致

package com.collection_;import java.util.Comparator;
import java.util.TreeMap;/*** @author Gao YongHao* @version 1.0*/
@SuppressWarnings({"all"})
public class TreeMap_ {public static void main(String[] args) {// 1. 构造器，把传入的实现了 Comparator接口的匿名内部类（对象），// 传给TreeMap的comparator属性/** public TreeMap(Comparator<? super K> comparator) {this.comparator = comparator;}** 2. 调用put方法* 2.1 第一次添加,把K-V封装到TreeMap$Entry对象中，由root指向，并退出*   Entry<K,V> t = root;if (t == null) {compare(key, key); // type (and possibly null) checkroot = new Entry<>(key, value, null);size = 1;modCount++;return null;}** 2.2 以后添加Comparator<? super K> cpr = comparator;if (cpr != null) {do { // 遍历所有的key，给当前的key找到适当的位置parent = t;cmp = cpr.compare(key, t.key);// 动态绑定到我们的匿名内部类的compare方法if (cmp < 0)t = t.left;else if (cmp > 0)t = t.right;elsereturn t.setValue(value);} while (t != null);}*** */TreeMap treeMap = new TreeMap(new Comparator() {@Overridepublic int compare(Object o1, Object o2) {// 定义排序规则return ((String) o1).compareTo(((String) o2));}});treeMap.put("jack", "杰克");treeMap.put("tom", "汤姆");treeMap.put("kristina", "克瑞斯提诺");treeMap.put("smith", "史密斯");treeMap.put(null, "史密斯");}
}

七、总结-开发中如何选择集合实现类(记住)

八、Collections工具类的使用

package com.collection_;import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;/*** @author Gao YongHao* @version 1.0*/
@SuppressWarnings({"all"})
public class Collections_ {public static void main(String[] args) {// 创建ArrayList集合，用于测试List list = new ArrayList();list.add("tom");list.add("smith");list.add("king");list.add("milan");// reverse(List)：反转 List 中元素的顺序Collections.reverse(list);// list=[milan, king, smith, tom]System.out.println("list=" + list);// shuffle(List)：对 List 集合进行随机排序Collections.shuffle(list);// list=[milan, tom, king, smith]System.out.println("list=" + list);//sort(List)：根据元素的自然顺序对指定 List 集合元素按升序排序Collections.sort(list);// list=[king, milan, smith, tom]System.out.println("list=" + list);// sort(List,Comparator)：根据指定的 Comparator 产生的顺序// 对 List 集合元素进行排序Collections.sort(list, new Comparator() {@Overridepublic int compare(Object o1, Object o2) {return ((String) o1).compareTo((String) o2);}});//list=[king, milan, smith, tom]System.out.println("list=" + list);// swap(List,int,int)：将指定 list 集合的 i 处元素和 j 处元素进行交换Collections.swap(list, 0, 1);// list=[milan, king, smith, tom]System.out.println("list=" + list);}
}

九、细节与例题

9.1 list综合题

package com.collection_;import java.util.ArrayList;
import java.util.List;/*** @author Gao YongHao* @version 1.0*/
public class List05 {@SuppressWarnings("all")public static void main(String[] args) {List list = new ArrayList();list.add(new Book("红楼梦", "曹雪芹", 100));list.add(new Book("西游记", "吴承恩", 10));list.add(new Book("水浒传", "施耐庵", 9));list.add(new Book("三国演义", "罗贯中", 80));list.add(new Book("西游记", "吴承恩", 10));boolean flag = true; // 表示是否一次都没交换// 走几趟for (int i = 0; i < list.size() - 1; i++) {for (int j = 0; j < list.size() - i - 1; j++) {Object o1 = list.get(j);Object o2 = list.get(j + 1);if (o1 instanceof Object && o2 instanceof Object) {Book bo1 = (Book) o1;double p1 = bo1.getPrice();Book bo2 = (Book) o2;double p2 = bo2.getPrice();if (p1 > p2) {list.set(j, bo2);list.set(j + 1, bo1);if (flag) flag = false;}}}if (flag) break;}for (Object o : list) {if (o instanceof Book) {Book book = (Book) o;System.out.println(String.format("名称:%s\t价格:%s\t作者:%s", book.getName(), book.getPrice(), book.getAuthor()));}}}
}

9.2 HashSet综合题

9.3 set的重复数据处理机制

// 重复数据的处理机制
package com.collection_;import java.util.HashSet;/*** @author Gao YongHao* @version 1.0*/
@SuppressWarnings({"all"})
public class Set01 {public static void main(String[] args) {HashSet set = new HashSet();// 说明:// 1. 在指执行add方法后，会返回一个boolean值// 2. 如果添加成功，返回 true，否则返回 falseSystem.out.println(set.add("john")); // TSystem.out.println(set.add("lucy")); // TSystem.out.println(set.add("john")); // F,后添加的失败System.out.println(set.add("jack")); // TSystem.out.println(set.add("Rose")); // T// 3. 可以通过 remove 指定删除哪个对象set.remove("john");System.out.println("set=" + set);// set=[Rose, lucy, jack]set = new HashSet();set.add("lucy"); // 添加成功set.add("lucy"); // 加入不了set.add(new Dog("tom")); // 添加成功set.add(new Dog("tom")); // 添加成功System.out.println("set=" + set); // set=[Dog{name='tom'}, Dog{name='tom'}, lucy]// 看源码，做分析，见 ---> 5.4 HashSet底层机制说明set.add(new String("hsp")); // 添加成功set.add(new String("hsp")); // 加入不了System.out.println("set=" + set); // set=[hsp, Dog{name='tom'}, Dog{name='tom'}, lucy]}
}

9.4 HashSet\HashMap\LinkedHashMap的数组扩容和红黑树转换机制

• HashSet的数组扩容时机：
  1、 当添加数据到链表上且链表元素个数小于8时：(未满足树化条件1)
  判断当前size是否大于等于Threshold 。若成立则扩容；不成立不进行操作
  2、 当添加数据到链表上且链表元素个数大于等于8时：(满足树化条件1)
  判断当前table数组长度是否大于等于64。成立则对链表进行树化（不扩容）；不成立则进行扩容(无需判断当前size是否大于等于Threshold)
  

package com.collection_;import java.util.HashSet;/*** @author Gao YongHao* @version 1.0*/
@SuppressWarnings({"all"})
public class HashSet02 {public static void main(String[] args) {HashSet hashSet = new HashSet();for (int i = 0; i < 100; i++) {// 源码// add() --> put() --> putVal()/** 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);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;}}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;if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)resize();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);}}*** */// 由于均是在链表上添加元素(hash相等但equals()还是Object继承下来的==)，// 每次添加一次均会查看链表元素个数是否已经大于等于8个(第一个树化条件)// 若满足条件则会进入 treeifyBin() 方法看是否满足另一树化条件:// 判断table数组长度是否大于等于64!!!// if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)//        resize();// 若满足则进行树化; 若不满足则进行扩容操作(注意此处没有判断元素个数是否大于threshold!)// capcity*=2   threshold*=2// 因此，在第8次添加时扩容 capcity:16(threshold=16*0.75=12) ---> capcity:32(threshold=32*0.75=24)// 在第9次添加时扩容 capcity:32(threshold=32*0.75=24) ---> capcity:64(threshold=64*0.75=48)// 在第10次添加时进行树化，不进行扩容!hashSet.add(i);}}
}class Human {private String name;@Overridepublic int hashCode() { // 自定义 hashCode 使每个 Human对象 的hashcode值相等return 100;}public Human(String name) {this.name = name;}
}

9.5 HashMap的hash函数原理

摘自：https://blog.csdn.net/wendelee/article/details/109848636?spm=1001.2101.3001.6661.1&utm_medium=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1.pc_relevant_default&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1.pc_relevant_default&utm_relevant_index=1

• 先看下 hash(Object key) 方法，详细大家基本都能看懂，但是知道这一步 (h = key.hashCode()) ^ (h >>> 16) 原因的人很少

    static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

• 首先这个方法的返回值还是一个哈希值。为什么不直接返回 key.hashCode() 呢？还要 与 (h >>> 16)异或。首先要了解以下知识点
  必备知识点.：^ 运算 >>>运算 &运算。

1、 h >>> 16 是什么，有什么用?
h是hashcode。h >>> 16是用来取出h的高16，(>>>是无符号右移) 如下展示：

0000 0100 1011 0011 1101 1111 1110 0001
>>> 16
0000 0000 0000 0000 0000 0100 1011 0011

2、 为什么 h = key.hashCode()) 与 (h >>> 16) 异或

• 讲到这里还要看一个方法indexFor，在jdk1.7中有indexFor(int h, int length)方法。jdk1.8里没有，但原理没变。下面看下1.7源码
  1.8中用tab[(n - 1) & hash]代替但原理一样。

static int indexFor(int h, int length) {return h & (length-1);
}

• 这个方法返回值就是数组下标。我们平时用map大多数情况下map里面的数据不是很多。这里与 （length-1）相 &,
• 但由于绝大多数情况下length一般都小于2^16即小于65536。所以 return h & (length-1); 结果始终是h的 低16位 与（length-1）进行&运算。如下例子（hashcode为四字节）
  

3、 原因总结

• 由于和 （length-1） 运算，length 绝大多数情况 小于2的16次方。所以始终是hashcode 的低16位（甚至更低）参与运算。要是高16位也参与运算，会让得到的下标更加散列。
• 所以这样高16位是用不到的，如何让高16也参与运算呢。所以才有hash(Object key)方法。让他的hashCode()和自己的高16位^运算。所以(h >>> 16)得到他的高16位与hashCode()进行^运算。(特殊的若高16位均为0则运算结果仍为低16位)

4、 为什么用^而不用&和|
因为&和|都会使得结果偏向0或者1 ,并不是均匀的概念,所以用^。 这就是为什么有hash(Object key)的原因。

5、 关于为什么数组长度要选择2的倍数

https://blog.csdn.net/weixin_32419787/article/details/113005001 — hashcode值指的是什么_Java 的 HashMap 中 hash 值的计算原理是什么？

9.6 List、Set与Map底层原理汇总

注：List接口中有 get 与 set 方法，其实现类均实现了get与set方法获取与修改值;而Set接口没有get与set方法，其实现类也没有自己的get与set方法可以调用。map的实现类使用put进行添加与修改操作

• List实现类：

  1. ArrayList（由数组实现）线程不安全
     1. 底层维护一个elementData 数组;
     2. 使用空构造器 elementData 数组初始为 空数组 {}；带参数则数组起始空间由传入参数设定;
     3. 使用空构造器后(或初始空间大小为0时)，第一次添加数据将 elementData 扩充至 10;
     4. 每次当空间不够时（剩余空间小于需要保存新元素的空间），扩充 1.5 倍
  2. LinkedList（由双向链表实现）线程不安全
     1. 底层维护 头结点属性 与 尾结点属性 (类型为 LinkedList 的 静态内部类Node);
     2. 添加数据是维护一个双向链表;
     3. 空间是动态的不需要扩容
  3. Vector（由数组实现）线程安全
     1. 实现与 ArrayList 类似，但 Vector 是线程安全的;
     2. 使用空构造器 elementData 数组初始大小 10；带参数则数组起始空间由传入参数设定;
     3. 每次当空间不够时（剩余空间小于需要保存新元素的空间），扩充 2 倍

• Set实现类：

  1. HashSet（数组+单向链表+红黑树）线程不安全
     1. 底层由 HashMap 实现；
     2. HashMap 维护了一个table数组（保存其静态内部类对象Node）;
     3. 使用 HashSet 第一次添加数据会扩充table数组至16(懒加载)，并同时维护一个 threshold 其大小等于 table`数组总容量 * 0.75 (当前16*0.75=12);
     4. 每次尝试添加一个数据时，会判断是否有“相同”的数据已经被存放在数组或链表中。判断重复的条件是：Hash值相等 且 （==为true 或 equals()为true）。若重复则将value作替换并返回该value值（value在HashSet设置了默认值），若没有重复则放入数组或链表中
     5. 扩容机制：
        1. 当满足第一个树化条件（在添加一个元素后一条单链表上长度达到了8），则判断第二个树化条件（当前table数组容量大于64）。不满足第二个树化条件则扩充table数组（容量扩充 2 倍）;
        2. 当不满足第一个树化条件，则每次添加一个元素后判断当前table数组中已有的数据总数(size)是否大于 threshold，大于则扩容，否则不扩;
     6. 树化机制：
        当添加一个元素后同时满足第一与第二树化条件则会将当前的单链表转换为一棵红黑树
  2. LinkedHashSet（数组+单向链表+红黑树+双向链表）线程不安全
     1. 底层是由 LinkedHashMap 实现，其继承 HashMap 维护一个父类table数组。同时其新维护了一条 双向链表：包含 头结点 对象 与 尾结点 对象（结点是LinkedHashMap的静态内部类 Entry 的对象，Entry继承了 HashMap 的静态内部类 Node）;
     2. 其判断重复、扩容机制与树化机制与 HashSet 相同；
     3. 每添加一个数据到父类table数组或链表，除了有 HashSet 相同的操作以外，还会额外的将新的数据封装至 Entry 结点中，并将该结点信息添加至 双向链表 中
     4. 该双向链表可使 LinkedHashSet 输出与输入相同顺序的数据
  3. TreeSet（二叉树）
     1. 底层是由TreeMap实现，它维护了 二叉树 根节点对象 TreeSet$Entry
     2. 在添加数据时，会使用到 Comparator接口的实现对象属性 comparator（Comparator 实现对象可以由构造器传入）。对于判别传入的k值与已有的k值是否重复使用comparator的compare方法；如没有传入Comparator 实现对象则要求传入的数据对象实现Comparable接口（二者必选其一）
     3. TreeSet 是根据 key 排序进行存储的，则要求 key 不能为null（即传入的值不能为null）

• Map实现类：

  1. HashMap(数组+单向链表+红黑树) 线程不安全

     1. 底层维护了一个table的HashMap$Node类型（它是Map.Entry的一个实现类）的数组
     2. 扩容与树化机制如HashSet中描述一致
     3. key可以为null值，但只能存在一个；value可以有多个null值
     4. HashMap中，后添加的k-v会替换原有的k相同的对应的v值
     5. entrySet方法返回一个EntrySet(Set的实现类)遍历table中的数据(HashMap$Node对象)
     6. keySet方法返回一个HashMap$KeySet（Set的实现类）遍历table中的数据的key值
     7. values方法返回一个HashMap$Values（Collection的实现类）遍历table中的数据的value值

  2. LinkedHashMap（继承自HashMap，底层 数组+单向链表+红黑树+双向链表）线程不安全

     1. 底层维护了父类的table数组（数据类型为LinkedHashMap$Entry，继承自HashMap$Node），还维护了一个双向链表的头结点对象与尾结点对象
     2. 保留了HashMap的数组+单链表+红黑树的结构，同时自己维护的双向链表保存了数据存入时的顺序，可使遍历得到与输入相同的顺序
     3. 扩容与树化机制与 HashMap 相同
     4. 也包含 entrySet()、keySet()、values() 方法

  3. HashTable（数组+单向链表）线程安全

     1. 底层维护了table数组（数据类型为HashTable$Entry，实现了Map.Entry）
     2. 其功能相当于没有树化机制（即没有红黑树）的HashMap
     3. 它是线程安全的
     4. 传入的Key与Value均不能为null

  4. Properties（继承自HashTable，数组+单向链表）

     • 底层维护与HashTable一样的数据结构。其扩展了对properteis文件的操作

  5. TreeMap（二叉树）

     1. 底层维护了一个 二叉树 的根节点（TreeMap$Entry）对象
     2. 存放机制与TreeSet描述一致
     3. 内部会根据key值进行顺序排序存储，要求 key 不能为null
     4. 同样要求 构造器传入Comparator 实现对象 或 传入的数据对象实现了Comparable接口（二者选一）

这篇关于十二、集合的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---