Java学习总结之集合（二）

1.HashMap集合底层是哈希表/散列表的数据结构

2.哈希表是一个数组和单向链表的结合体

3.HashMap集合底层的源代码如下：

源代码：
public class HashMap{
//HasMap底层实际上就是一个数组（一维数组）
    Node[] table;
    static class Node implements Map.Entry {
        final int hash;//哈希值hash
        final K key;//存储到Map集合中的key
        V value;//存储到Map集合中的value
        Node next;//下一个节点的内存地址
//哈希值是key的hashCode()方法的执行结果，hash通过哈希函数/算法可以转换存储成数组的下标
//哈希表/散列表：一维数组，这个数组中每一个元素是一个单向链表
}

4.map.put(K,V)实现原理：
   第一步：先将k，v封装到Node对象中
   第二步：底层会调用k的hashCode()方法得出hash值，然后通过哈希函数/算法将hash值转换成数组的下标，下标位置上如果没有任何元素，就把Node添加到这个位置上。如果下标对应的位置上有Node链表，此时会拿着k和链表上每一个节点中的k进行equals，如果所有的equals方法返回都是false，那么这个节点将会被添加到链表的末尾。如果其中有一个equals返回了true，那么这个节点的value将会被覆盖

5.v = map.get(k)实现原理
   先调用k的hashCode()方法得出哈希值，通过哈希算法转换成数组下标，通过数组下标快速定位到某个位置上，如果这个位置上什么也没有返回null，如果这个位置上有单向链表，那么会拿着参数k和单向链表上的每个节点中的k进行equals，如果所有equals方法返回false那么get方法返回null，只要有其中一个节点的k和参数k进行equals时返回true，那么此时该节点的value就是我们要找的value，get方法最终返回这个要找的value

6.为什么哈希表的随机增删和查询效率都很高？
   增删是在链表上完成，查询也不需要都扫描，只需要部分扫描。

注意！HashMap集合的key会先后调用hashCode()方法和equals()方法，并且这两个方法都需要重写

7.HashMap集合的key部分特点
   无需不可重复。
   为何无序？因为不一定挂到哪个单向链表上。
   如何保证不可重复？equals方法来保证HashMap集合的key不可重复，如果key重复了value会覆盖。HashMap集合允许key和value为null,但是HashMap集合key的null只能有一个。HashTable不允许key为null,也不允许value为null。放在HashMap集合key部分的元素其实就是放到HashSet集合中了。
   放在Map集合key部分的元素其实就是放在HashSet集合中，所以HashSet集合中的元素也需要同时重写hashCode()+equals()方法

注意！同一个单向链表上所有节点的hash相同，因为他们的数组下标是一样的，但同一个链表上k和k的equals方法肯定返回的是false，都不相等。

8.哈希表HashMap使用不当时无法发挥性能！
（1）若将所有的hashCode()方法返回值固定为某一个值，那么会导致底层哈希表变成了一个纯单向链表。这种情况我们称为：散列分部不均匀
那么，什么是散列分部均匀？
假设有100个元素和10个单向链表，那么每个单向链表上有10个结点，这是最好的，称为散列分布均匀。
（2）若将所有的hashCode()方法返回值都设定为不一样的值，会导致底层哈希表变成了一个一维数组，没有链表的概念，也是散列分布不均匀

9.重点：放在HashMap集合key部分的元素以及放在HashSet集合中的元素需要同时重写hashCode()和equals方法

10.HashMap集合的默认初始容量是10，默认加载因子是0.75，这个默认加载因子是当HashMap集合底层的数组容量达到75%的时候数组开始扩容。
   注意！HasMap集合的初始化容量必须是2的倍数，这也是官方推荐的。因为这是达到散列分布均匀为了提高HashMap集合的存取效率所必须的。

11.向Map集合中存以及从Map集合中取都是先调用的key的hashCode()方法然后再调用equals方法，equals方法有可能调用也有可能不调用。
（1）拿put(k,v)举例，什么时候equals不会调用？
k.hashCode()方法返回哈希值，哈希值通过经过哈希算法转换成数组下标，数组下标位置上如果是null，equals不需要执行。
（2）拿get(k,v)举例，什么时候equals方法不会调用？
k.hashCode()方法返回哈希值，哈希值经过哈希算法转换成数组下标，数组下标位置上如果是null，equals不需要执行。

12.注意！如果一个类的equals方法重写了，那么hashCode()方法必须重写，并且equals方法如果返回是true，hashCode()方法返回值必须一样。

13.在JDK8之后，如果哈希表单向链表中元素超过8个，单向链表这种数据结构会变成红黑树数据结构。当红黑树上的节点数量小于6时，会重新把红黑树变成单向链表数据结构，这种方式也是为了提高检索效率，二叉树的检索会再次缩小扫描范围，提高效率。HasMap集合的key和value允许null，扩容之后的容量是原容量的2倍。

1.Properties是一个Map集合，继承Hashtable，Properties的key和value都是String类型

2.Properties被称为属性类，是线程安全的

1.TreeSet集合底层实际上是一个TreeMap，是一个二叉树

2.放到TreeSet集合的元素等同于放到TreeMap集合的key部分

3.TreeSet集合中的元素：无序不可重复，但是可以按照元素的大小自动排序，称为：可排序集合

4.TreeSet无法对自定义类型排序

1.自平衡二叉树遵循左小右大原则存放

2.遍历二叉树时有三种方式：
前序遍历：根左右
中序遍历：左根右
后序遍历：左右根
注意！前中后说的是：“根”的位置

3.TreeSet集合/TreeMap集合采用的是中序遍历方式，Iterator迭代器采用的是中序遍历方式：左根右

4.放到TreeSet集合/TreeMap集合的元素要想做到排序，包括以下两种方式：
（1）放在集合中的元素实现java.lang.Comparable接口
（2）在构造TreeSet集合/TreeMap集合的时候给他传一个比较器对象

5.Comparable和Comparator如何选择？
   当比较规则不会发生改变的时候，或者说当比较规则只有1个时，建议实现Comparable接口；如果比较规则有多个并且需要多个比较规则直接频繁切换，建议使用Comparator接口，Comparator接口的设计符合OCP原则

1.java.util.Collection（集合接口）

2.java.util.Collections（集合工具类）

注意！对List集合中元素排序，需要保证List集合中的元素实现了Comparable接口。

1.每个集合对象的创建

2.向集合中添加元素

3.从集合中取出某个元素

4.遍历集合

5.主要的集合类：ArrayList、linkedList、HashSet、TreeSet、HashMap、Properties、TreeMap