LinkedHashSet
LinkedHashSet：是HashSet的子类，无相关自己实现的类。其中实际上使用的是LinkedHashMap(同样是HashMap子类)，能够顺序访问插入进来的数。
底层使用的是数组+双向链表形式，其中访问数据都是有序的。如下图清晰看出为什么能够顺序访问存储的数据：
要求：向Set中添加的数据，其所在类一定要重写hashCode()与equals()方法。极可能保持两个方法一致性。
说明：LinkedHashSet插入性能略低于HashSet，但在迭代访问Set里的全部元素有很好的性能。
TreeSet
TreeSet：是 SortedSet 接口的实现类，可以确保元素处于排序状态，底层使用红黑树结构存储数据。
两种排序方式：自然排序与定制排序。默认情况下采用自然排序(map根据key自然排序)。
特点：有序，查询速度比List快。
两种排序实现
默认是使用的自然排序(很多类中本身就实现了Comparable，add()添加中调用public int compareTo(T o);即可进行比对)；另一种则是定制排序，需要实现Comparable接口传入到TreeSet构造器中，见如下：
自然排序：
import java.util.*; public class Main { public static void main(String[] args) { TreeSet<Person> set = new TreeSet<>(); set.add(new Person("changlu",12)); set.add(new Person("liner",10)); set.add(new Person("changlu",8)); //遍历 Iterator<Person> iterator = set.iterator(); while(iterator.hasNext()){ System.out.println(iterator.next()); } } } class Person implements Comparable{ private String name; private Integer age; public Person(String name, Integer age) { this.name = name; this.age = age; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Person person = (Person) o; if (name != null ? !name.equals(person.name) : person.name != null) return false; return age != null ? age.equals(person.age) : person.age == null; } @Override public int hashCode() { int result = name != null ? name.hashCode() : 0; result = 31 * result + (age != null ? age.hashCode() : 0); return result; } @Override public int compareTo(Object o) { if(o instanceof Person){ Person p = (Person) o; //先按照String排序 int result = this.name.compareTo(p.name); if(result == 0){//0表示相等 return this.age.compareTo(p.age); } return result; }else{ throw new RuntimeException("类型不匹配"); } } @Override public String toString() { return "Person{" + "name='" + name + '\'' + ", age=" + age + '}'; } }
自然排序就是会根据添加类中通过实现Comparable接口实现的compareTo方法来进行比对添加。对于一些JDK中提供的类已经实现了Compareable接口，而自定义的则需要手动实现该接口并实现其方法。
重写equals()、hashCode()法是为了让Set集合中不出现重复的元素，compareTo方法是去实现排序的效果。
自定义排序：
import java.util.*; public class Main { public static void main(String[] args) { //实现一个匿名接口类，实现其中的方法，让字符串倒序排列 Comparator<String> comparator = new Comparator<String>() { @Override public int compare(String o1, String o2) { return -o1.compareTo(o2); } }; TreeSet<String> set = new TreeSet<String>(comparator); set.add("changlu"); set.add("liner"); //遍历 Iterator<String> iterator = set.iterator(); while(iterator.hasNext()){ System.out.println(iterator.next()); } } }
通过实现Comparator的匿名接口类将其放入到TreeSet的构造器中，之后执行add()方法则里排序会根据Comparator中的compareTo方法进行比对。
源码分析
下面只是我自己简单的分析：
//TreeSet源码 public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable{ private transient NavigableMap<E,Object> m; public TreeSet() { //实际上创建了TreeMap的实例 this(new TreeMap<E,Object>()); } //实际上调用了TreeMap的有参构造传入了comparator(即定制排序) public TreeSet(Comparator<? super E> comparator) { this(new TreeMap<>(comparator)); } //执行添加操作实际上就是调TreeMap的put()方法 public boolean add(E e) { return m.put(e, PRESENT)==null; } ... } //TreeMap源码 public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable{ //内部comparator实例 private final Comparator<? super K> comparator; //该构造器将外部自定义comparator引用传给内部属性 public TreeMap(Comparator<? super K> comparator) { this.comparator = comparator; } //put()方法：其中就会根据情况使用自然排序或者定制排序 public V put(K key, V value) { ... Comparator<? super K> cpr = comparator;//接收本类中的comparator(初始为null) if (cpr != null) {//这里就是判断是使用自然排序还是定制排序 //不为null表示，说明我们之前传入了Comparator实例，使用定制排序 do { parent = t; cmp = cpr.compare(key, t.key);//执行实现了compare()方法 if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } else { //使用自然排序，一般就是直接调集合元素中的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; else return t.setValue(value); } while (t != null); } ... } }
粗略的看了下源码，这里只针对使用自然排序还是定制排序进行分析
Set相关面试题
(1)、在list中取出重复数字值，要求尽量简单
import java.util.*; public class Main { public static List<Integer> duplicateList(List<Integer> list){ HashSet<Integer> set = new HashSet<>(list);//或者使用set.addAll(list)添加 return new ArrayList<>(set); } public static void main(String[] args) { List<Integer> list = new ArrayList<>(); list.add(12); list.add(15); list.add(12); list.add(26); list.add(15); list = duplicateList(list); //遍历 Iterator<Integer> iterator = list.iterator(); while(iterator.hasNext()){ System.out.println(iterator.next()); } } }
(2)、hashset增加或删除值的判断
class Person{ public String name; public int age; public Person() { } public Person(String name, int age) { this.name = name; this.age = age; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Person person = (Person) o; if (age != person.age) return false; return name != null ? name.equals(person.name) : person.name == null; } @Override public int hashCode() { int result = name != null ? name.hashCode() : 0; result = 31 * result + age; return result; } @Override public String toString() { return "Person{" + "name='" + name + '\'' + ", age=" + age + '}'; } } public class exerTest { @Test public void test(){ HashSet hashSet = new HashSet(); Person p = new Person("Tom",100); Person p1 = new Person("Tom1",101); hashSet.add(p); hashSet.add(p1); System.out.println(hashSet);//[Person{name='Tom', age=100}, Person{name='Tom1', age=101}] p.age = 102; hashSet.remove(p); System.out.println(hashSet);//[Person{name='Tom', age=102}, Person{name='Tom1', age=101}] hashSet.add(new Person("Tom",102)); System.out.println(hashSet); //[Person{name='Tom', age=102}, Person{name='Tom', age=102}, Person{name='Tom1', age=101}] hashSet.add(new Person("Tom",100)); System.out.println(hashSet); //[Person{name='Tom', age=102}, Person{name='Tom', age=102}, Person{name='Tom1', age=101}, Person{name='Tom', age=100}] } }
50行修改原先p的age值，接着执行remove()方法删除无效，过程：首先比对hashcode值，找到了确定位置，接着使用equals()方法比较值，没有相同的，所以删除失败。
第54行添加了一个对象，这里添加成功，过程：首先会推出hashcode值，没有与之相同的则会直接添加。注意这里添加的虽然和之前修改的一个对象属性相同，但是hashcode值不同，所以添加成功。
第58行我们又添加了一个对象，这个对象中的属性与原来没有修改的p相同，所以hashcode值与p是同一个位置，接着使用equals()方法比对，发现没有值与其相同，最后添加成功。
hashCode()方法重写介绍 class Person{ String name; Integer age; //这是通过IDEA生成的hashCode()方法 @Override public int hashCode() { int result = name != null ? name.hashCode() : 0; result = 31 * result + (age != null ? age.hashCode() : 0); return result; } }
result是本地方法得到的一个hash值，选择一个系数值31与result相乘。
选择系数的时候要选择尽量大的稀疏，如果计算出来的hash地址越大，所谓的冲突也就越少，查找起来效率也会提高(减少冲突)。
这里的31也可以使用i*31=(i<<5)-1，乘以2*5-1=31，很多虚拟机中都有相关优化。(提高算法效率)
31是一个素数，数组作用就是如果我用一个数字来乘以这个素数，最终出来的结果只能被本身和被乘数还有1来整除！(减少冲突)
Map接口及常用实现类
Map接口
Map接口：就是一个单独的接口interface Map<K,V> ，用于保存具有映射关系的数据:key-value，key与value都可以是任何引用类型的数据。
key使用Set来存放，不允许重复，即同一个Map对象所对应的类必须重写equals()、hashCode()方法。一般使用String类作为key。
通过指定的key总能找到唯一、确认的value。
key使用的是Set(无序、不可重复)，Values使用的Collection存储(无序、可重复)，每个键值对则为Entry(无序、不可重复)。
常用实现类：
HashMap：作为Map的主要实现类：线程不安全，效率高；可以存储null的key与value。
LinkedHashMap：保证在遍历map元素时，可以按照添加的顺序实现遍历。
原因：在原本的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个元素。对于频繁的遍历操作，执行效率比HashMap高。
TreeMap：按照添加的key-value进行排序，实现排序遍历。会考虑key的自然排序或定制排序，底层使用了红黑树。
HashTable：线程安全，效率低，不能存储为null的key和value(若是value为空直接手动抛出异常，而key报异常是因为调用了key的hashcode()方法若为null则是空指针)。
Properties：常用来处理配置文件，key和value都是String类型。
针对于HashMap、LinkedHashMap想要构造一个线程安全的则可用Collections.synchronizedMap(new HashMap(...))
针对于TreeMap想要构造线程安全的可用Collections.synchronizedSortedMap(new TreeMap(...)) 。
常用方法：
HashMap
HashMap：是利用哈希表原理来存储元素的集合，有两个参数影响性能：初始容量和加载因子。
不同版本变化：
JDK7：底层是数组+链表(链地址法)。
JDK8：数组+链表(或红黑树)
不同版本底层实现原理
JDK7的实现原理如下：
简述：初始创建长度为16的数组，执行put()后，首先获取哈希值来得到存放位置，判断当前位置是否为空，为空插入成功；不为空来去比对其中的哈希值是否相同，若都不相同则添加成功；若相同，再比较equals()方法若是返回false添加成功，返回true为失败。
扩容情况：扩容2倍。
JDK8的实现原理如下：
同样也是扩容2倍。
转换不同数据结构：当HashMap中的其中一个链的对象个数如果达到了8个，此时如果capacity没有达到64，那么HashMap会先扩容解决，如果已经达到了64，那么这个链会变成树，结点类型由Node变成TreeNode类型。当然，如果当映射关系被移除后， 下次resize方法时判断树的结点个数低于6个，也会把树再转为链表。
若是我们已知HashMap中的元素个数，建议预设元素个数能够有效提升HashMap的性能。
重要常量
DEFAULT_INITIAL_CAPACITY : HashMap的默认容量，16。
MAXIMUM_CAPACITY ： HashMap的最大支持容量，2^30 。
DEFAULT_LOAD_FACTOR：HashMap的默认加载因子 。
TREEIFY_THRESHOLD：Bucket中链表长度大于该默认值，转化为红黑树 。
UNTREEIFY_THRESHOLD：Bucket中红黑树存储的Node小于该默认值，转化为链表 。
MIN_TREEIFY_CAPACITY：桶中的Node被树化时最小的hash表容量。（当桶中Node的 数量大到需要变红黑树时，若hash表容量小于MIN_TREEIFY_CAPACITY时，此时应执行 resize扩容操作这个MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4 倍。）
table：存储元素的数组，总是2的n次幂 。
entrySet：存储具体元素的集 。
size：HashMap中存储的键值对的数量 。
modCount：HashMap扩容和结构改变的次数。
threshold：扩容的临界值，=容量*填充因子 loadFactor：填充因子。
LinkedHashMap
LinkedHashMap：是HashMap的子类，在HashMap存储结构基础上，使用了双向链表来记录添加元素的顺序。与LinkedHashSet类似，LinkedHashMap可以维护Map的迭代顺序(与插入顺序一致)。
看一下HashMap中的内部类及LinkedHashMap中的内部类：
//HashMap中的内部类Node static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; ... } //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); } }
与HashMap不同之处就是维护了这个Entry双向链表，通过该Entry来保存前后顺序
TreeMap
TreeMap：底层是红黑树，存储 Key-Value 对时，需要根据 key-value 对进行排序。保证所有的 Key-Value 对处于有序状态。对于TreeMap可以使用自然排序与定制排序(可看前面TreeSet)，注意是对key进行排序。
TreeMap的containsKey、get、put、remove方法提供了log(n)的时间开销。
HashTable
HashTable：线程安全(方法都上了锁)，实现了一个哈希表，能够将键映射到值，key与value都不能为空。
源码分析：看一下为什么key与value不为为空
public synchronized V put(K key, V value) { // Make sure the value is not null if (value == null) {//一旦value为空则抛出异常 throw new NullPointerException(); } // Makes sure the key is not already in the hashtable. Entry<?,?> tab[] = table; int hash = key.hashCode();//若为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; return old; } } addEntry(hash, key, value, index); return null; }
Properties
Properties：是HashTable的子类，该对象用于处理属性文件，其中的key、value值都是String类型的。
常用于读取properties配置文件，读取方法一般使用：setProperty(String key,String value)方法和 getProperty(String key)
实际上这个类给我们封装了文件读取流的操作，可从配置文件中读取key、value键值对存储到Map集合中，接着我们使用方法来获取键值对，一般使用于读取数据库配置文件：
实例演示
public static void main(String[] args) { Properties properties = new Properties(); try { properties.load(new FileInputStream("jdbc.properties")); String username = properties.getProperty("username"); String password = properties.getProperty("password"); System.out.println(username+":"+password); } catch (IOException e) { e.printStackTrace(); } }
一行写一对key、value键值对，查看源码是每次读取一行
Map遍历方法
public static void main(String[] args) { Map<String,Integer> map = new HashMap<>(); map.put("changlu",18); map.put("liner",21); //遍历key Set<String> set = map.keySet(); for (String s : set) { System.out.println(s); } //遍历value Collection<Integer> values = map.values(); for (Integer value : values) { System.out.println(value); } //遍历Entry Set<Map.Entry<String, Integer>> entries = map.entrySet(); for (Map.Entry<String, Integer> entry : entries) { System.out.println(entry.getKey()+":"+entry.getValue()); } }
keySet()：获取由所以的key组成的set集合
values()：获取由所有的value组成的collection集合。
entrySet()：获取包含key、value的set集合。
相关面试题
例1：负载因子值的大小，对HashMap有什么影响
负载因子的大小决定了HashMap的数据密度。
负载因子越大密度越大，发生碰撞的几率越高，数组中的链表越容易长, 造成查询或插入时的比较次数增多，性能会下降。
负载因子越小，就越容易触发扩容，数据密度也越小，意味着发生碰撞的 几率越小，数组中的链表也就越短，查询和插入时比较的次数也越小，性 能会更高。但是会浪费一定的内容空间。而且经常扩容也会影响性能，建 议初始化预设大一点的空间。
按照其他语言的参考及研究经验，会考虑将负载因子设置为0.7~0.75，此时平均检索长度接近于常数。
四、Collections工具类
单独一个分支，是一个包装类。
Collections：是一个操作Set、List、Map等集合的工具类，提供了一系列静态方法来对集合元素进行排序、查询、修改等操作，提供了对集合对象设置不可变，对集合对象实现同步控制等方法(上锁)。
Arrays：是一个操作数组的工具类
相关方法
排序方法：
reverse(List)：反转 List 中元素的顺序 。
shuffle(List)：对 List 集合元素进行随机排序 。
sort(List)：根据元素的自然顺序对指定 List 集合元素按升序排序 。
sort(List，Comparator)：根据指定的 Comparator 产生的顺序对 List 集合元素进行排序 。
swap(List，int， int)：将指定 list 集合中的 i 处元素和 j 处元素进行交换。
查找,替换方法：
Object max(Collection)：根据元素的自然顺序，返回给定集合中的最大元素 。
Object max(Collection，Comparator)：根据 Comparator 指定的顺序，返回 给定集合中的最大元素。
Object min(Collection) ：根据元素的自然顺序，返回给定集合中的最小元素 。
Object min(Collection，Comparator) ：根据 Comparator 指定的顺序，返回 给定集合中的最小元素 。
int frequency(Collection，Object)：返回指定集合中指定元素的出现次数。
void copy(List dest,List src)：将src中的内容复制到dest中 。
boolean replaceAll(List list，Object oldVal，Object newVal)：使用新值替换 List 对象的所有旧值。
同步控制方法：将指定集合包装成线程同步的集合，从而解决多线程并发访问集合时的线程安全问题。
public static Collection synchronizedCollection(Collection c);
public static Set synchronizedSet(Set s);
public static List synchronizedList(List list);
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m);
public static SortedSet synchronizedSortedSet(SortedSet s);：例如TreeSet。
public static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m);：例如TreeMap。
参考资料
[1]. fail-fast
[2]. 真正搞懂hashCode和hash算法（面试官都馋哭了）
[3]. 面试常问：什么是红黑树？
[4]. 尚硅谷_Java零基础教程-java入门必备-适合初学者的全套完整版教程(宋红康主讲)
