刨析源码，深层讲解 Java-集合框架( 十 ) _链表

负载因子越小，就越容易触发扩容，数据密度也越小，意味着发生碰撞的几率越小，数组中的链表也就越短，查询和插入时比较的次数也越小，性能会更高。但是会浪费一定的内容空间。而且经常扩容也会影响性能，建议初始化预设大一点的空间。
按照其他语言的参考及研究经验，会考虑将负载因子设置为0.7~0.75，此时平均检索长度接近于常数。
4. Map实现类之二： 4.1 概述
?是的子类。
? 在存储结构的基础上，使用了一对双向链表来记录添加元素的顺序。
? 与类似，可以维护 Map 的迭代顺序：迭代顺序与 Key-Value对的插入顺序一致，保证在遍历map元素时，可以按照添加的顺序实现遍历。
原因：在原有的底层结构基础上，添加了一对指针，指向前一个和后一个元素。
? 对于频繁的遍历操作，此类执行效率高于。
4.2 底层结构
? 中的内部类：Node
static class Node implements Map.Entry {final int hash;final K key;V value;Node next; }
? 中的内部类：Entry
static class Entry extends HashMap.Node {Entry before, after;Entry(int hash, K key, V value, Node next) {super(hash, key, value, next);} }
5. Map实现类之三： 5.1 概述
? 存储 Key-Value 对时，需要根据 key-value 对进行排序。
?可以保证所有的 Key-Value 对处于有序状态。
? 底层使用红黑树结构存储数据。
? 保证按照添加的key-value对进行排序，实现排序遍历。此时考虑key的自然排序或定制排序：
自然排序：的所有的 Key 必须实现接口，而且所有的 Key 应该是同一个类的对象，否则将会抛出
定制排序：创建时，传入一个对象，该对象负责对中的所有 key进行排序。此时不需要 Map 的 Key 实现接口
? 判断两个key相等的标准：两个key通过()方法或者()方法返回0 。
5.2 代码演示
public class TreeMapTest {//向TreeMap中添加key-value，要求key必须是由同一个类创建的对象//因为要按照key进行排序：自然排序、定制排序//自然排序@Testpublic void test1(){TreeMap map = new TreeMap();User u1 = new User("Tom",23);User u2 = new User("Jerry",32);User u3 = new User("Jack",20);User u4 = new User("Rose",18);map.put(u1,98);map.put(u2,89);map.put(u3,76);map.put(u4,100);Set entrySet = map.entrySet();Iterator iterator1 = entrySet.iterator();while (iterator1.hasNext()){Object obj = iterator1.next();Map.Entry entry = (Map.Entry) obj;System.out.println(entry.getKey() + "---->" + entry.getValue());}}//定制排序@Testpublic void test2(){TreeMap map = new TreeMap(new Comparator() {@Overridepublic int compare(Object o1, Object o2) {if(o1 instanceof User && o2 instanceof User){User u1 = (User)o1;User u2 = (User)o2;return Integer.compare(u1.getAge(),u2.getAge());}throw new RuntimeException("输入的类型不匹配！");}});User u1 = new User("Tom",23);User u2 = new User("Jerry",32);User u3 = new User("Jack",20);User u4 = new User("Rose",18);map.put(u1,98);map.put(u2,89);map.put(u3,76);map.put(u4,100);Set entrySet = map.entrySet();Iterator iterator1 = entrySet.iterator();while (iterator1.hasNext()){Object obj = iterator1.next();Map.Entry entry = (Map.Entry) obj;System.out.println(entry.getKey() + "---->" + entry.getValue());}}}
6. Map实现类之四： 6.1 概述
? 是个古老的 Map 实现类，JDK1.0就提供了。不同于，是线程安全的，但效率低；不能存储null的key和value 。
? 实现原理和相同，功能相同。底层都使用哈希表结构，查询速度快，很多情况下可以互用。
?与的比较
与不同，不允许使用 null 作为 key 和 value。