哈希表（散列表，非线性结构）：

• 优点：提供了键（Key）和值 （Value）的映射关系，只要给出一个Key，就可以高效查找到它所匹配的Value，查询、插入和删除时间复杂度接近于O(1)
• 缺点：哈希表底层是基于数组的，数组有最大容量，所以当哈希表接近满容量时，性能下降严重，将哈希表进行扩容效率低

哈希表：链地址法来解决哈希冲突（数组+链表）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

public class HashTable {

    private int size;
    private Node[] table;//链表数组

    public HashTable(int size) {
        this.size = size;
        table = new Node[size];
    }

    //如果索引位置没有节点，则将新节点放置在该位置。否则，遍历索引位置的链表，直到找到最后一个节点，并将新节点添加到末尾
    public void put(String key, String value) {
        int index = getIndex(key);
        Node node = new Node(key, value);
        if (table[index] == null) {
            table[index] = node;
        } else {
            Node current = table[index];
            while (current.next != null) {
                current = current.next;
            }
            current.next = node;
        }
    }

    //根据关键字找到索引位置，然后遍历链表，直到找到具有相同键的节点或到达链表结尾。如果找到具有相同键的节点，则返回其值，否则返回null
    public String get(String key) {
        int index = getIndex(key);
        Node node = table[index];
        while (node != null) {
            if (node.key.equals(key)) {
                return node.value;
            }
            node = node.next;
        }
        return null;
    }

    //散列函数：使用Java内置的hashCode方法来计算关键字的哈希值，并将其模数为哈希表的大小来得到索引位置
    private int getIndex(String key) {
        int hashCode = key.hashCode();
        int index = hashCode % size;
        return index;
    }

    //链表结点类
    private class Node {
        String key;
        String value;
        Node next;

        public Node(String key, String value) {
            this.key = key;
            this.value = value;
        }
    }
}

Java 哈希表：

1. HashTable

   继承关系：

   • Map接口：键值对 key➡value 的形式保存，key不能重复
     *Dictionary类（废弃）
     * HashTable类（线程安全）

   哈希冲突概念：不同的key，通过相同的哈希函数计算出相同的哈希地址，这种现象称为哈希冲突或者哈希碰撞

   底层源码分析：

   • HashTable底层采用数组+链表方式
   • HashTable底层数组造对象就创建
   • HashTable所有的操作都是通过synchronized锁保护实现的，只有获得了对应的锁，才能进行后续的读写操作保证了线程安全，但效率低
   • HashTable不能存储null的key和value
   • HashTable的默认数组容量大小为11，负载因子为0.75，数组中元素个数如果等于负载容量，则进行扩容操作，默认扩容为原来两倍加一（保证数组长度尽量为素数或者奇数有利于计算数组下标时数组下标更加均匀，减少Hash碰撞）
   • HashTable计算key的hash值（数组的下标）通过取模方式
   • HashTable采用头插法的方式插入元素
   • HashTable利用put()方法添加元素时，先计算待添加元素中key的hash值获取插入位置（数组下标），看该位置是否已经有元素存在，若无元素存在，直接插入待添加元素；若有元素存在，逐一比较待添加元素和已存在元素的key的hash值，值不同则以链表的方式直接插入待添加的元素（头插法），值相同再调用待添加元素的equals（）方法进行key值的二级比较，二级比较过后，相同则将已存在元素的value值进行替换，不同则直接插入待添加的元素（确认该元素需要添加后put()方法会调用addEntry()方法进行插入操作，会先判断数组是否需要扩容，如果需要扩容，扩容后重新计算插入位置，再进行插入操作，如果不需要扩容，直接进行插入操作）；

   常用方法：

   Map接口：

   （1）V put(K key, V value);向集合中添加元素

   （2）V get(Object key);通过指定key获取value。

   （3）int size();获取集合中元素的个数。

   （4）void clear();清空集合，元素个数变为0。

   （5）boolean isEmpty();判断集合元素个数是否为0。

   （6）boolean containsKey(Object key);判断集合中是否包含指定key。

   （7）boolean containsValue(Object value);判断集合中是否包含指定value。

   注意：contains()方法底层都调用了equals()方法，再次强调存入集合元素的类一定要重写equals()方法。

   （8）Set<泛型> keySet();获取集合中所有的key，返回一个包含所有key元素的Set集合。

   （9）Collection values();获取集合中所有的value，返回一个包含所有value元素的Collection集合。

   （10）V remove(Object key);删除指定key的键值对。

   （11）default boolean replace(K key, V oldValue, V newValue);修改键值对< key, oldValue >的value为newValue。

   （12）Set< Map.Entry< K,V > > entrySet();将Map集合转换成Set集合。

   HashTable 特有：

   （1）void clear()：将此哈希表清空，使其不包含任何键。

   （2）Object clone()：创建此哈希表的浅表副本。

   （3）boolean contains(Object value)：测试此映射表中是否存在与指定值关联的键。

   （4）boolean containsKey(Object key):测试指定对象是否为此哈希表中的键。

   （5）boolean containsValue(Object value)：如果此 Hashtable 将一个或多个键映射到此值，则返回 true。

   （6）Enumeration elements()：返回此哈希表中的值的枚举。

   （7）Object get(Object key)：返回指定键所映射到的值，如果此映射不包含此键的映射，则返回 null. 更确切地讲，如果此映射包含满足 (key.equals(k)) 的从键 k 到值 v 的映射，则此方法返回 v；否则，返回 null。

   （8）boolean isEmpty()：测试此哈希表是否没有键映射到值。

   （9）Enumeration keys()：返回此哈希表中的键的枚举。

   （10）Object put(Object key, Object value)： 将指定 key 映射到此哈希表中的指定 value。

   （11）void rehash()：增加此哈希表的容量并在内部对其进行重组，以便更有效地容纳和访问其元素。

   （12）Object remove(Object key)：从哈希表中移除该键及其相应的值。

   （13）int size():返回此哈希表中的键的数量。

   （14）String toString():返回此 Hashtable 对象的字符串表示形式，其形式为 ASCII 字符 “, “ （逗号加空格）分隔开的、括在括号中的一组条目。

2. HashMap

   继承关系：

   • Map接口：键值对 key➡value 的形式保存，key不能重复
     • AbstractMap类
       • HashMap类（线程不安全）

   底层源码分析：

   • HashMap底层在jdk8之前采用数组+链表方式，jdk8采用数组+链表+红黑树方式
   • HashMap线程不安全
   • HashMap可以存储null的key和value
   • HashMap的默认数组容量大小为16，负载因子为0.75，数组中元素个数如果等于负载容量，则进行扩容操作，默认扩容为原来两倍
   • HashMap计算key的hash值（数组下标）通过位运算方式
   • HashMap采用尾插法的方式插入元素（jdk8）
   • HashMap利用put()方法添加元素时（和HashTable一样），先计算待添加元素中key的hash值获取插入位置（数组下标），看该位置是否已经有元素存在，若无元素存在，直接插入待添加元素；若有元素存在，逐一比较待添加元素和已存在元素的key的hash值，值不同则以链表的方式直接插入待添加的元素（头插法），值相同再调用待添加元素的equals（）方法进行key值的二级比较，二级比较过后，相同则将已存在元素的value值进行替换，不同则直接插入待添加的元素（确认该元素需要添加后put()方法会调用addEntry()方法进行插入操作，会先判断数组是否需要扩容，如果需要扩容，扩容后重新计算插入位置，再进行插入操作，如果不需要扩容，直接进行插入操作）；
   • 当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64时，此时此索引位置上的所数据改为使用红黑树存储。（jdk8）
   • jdk8时HashMap底层数组延迟在添加元素时创建，jdk8前造对象就创建

   采用方法：

   （1）put()方法 往集合中添加元素，key 值不可重复，重复时会覆盖之前的 value 值

   （2）size()方法 返回集合长度

   （3）get(key)方法 获取对应 key 值的 value 值

   （4）clear()方法 清除集合中的所有元素

   （5）values()方法 返回一个新集合，获取集合中所有元素的 values

   （6）keySet()方法 返回一个新集合，获取集合中所有元素的 key

   （7）remove()方法 根据 key 或者 key-value 去除集合中元素，并分别返回 value 值和 Boolean 值

   （8）iterator()方法 返回一个迭代器对象

   （9）entrySet()方法 将 Map 集合每个 key-value 转换为一个 Entry 对象，并返回由所有的 Entry 对象组成的Set 集合

   （10）containsKey() 判断集合中是否含右指定的 key 值

HashMap与HashTable区别

• HashMap线程不安全；HashTable线程安全（效率低）
• Hashmap是允许key和value为null值的，HashTable键值对都不能为空，否则包空指针异常
• HashMap计算key的hash值通过位运算方式；HashTable通过取模方式（效率低）
• HashMap 哈希扩容必须要求为原容量的2倍，Hashtable扩容为原容量2倍加1
• HashMap解决冲突时，如果冲突数量小于8，则是以链表方式存储，当冲突大于等于8时，就会转换为红黑树进行存储，当树的冲突数量小于6时，则又转化为链表存储（jdk8）；HashTable一直以链表进行存储
• HashMap链表采用尾插法的方式插入元素（jdk8）；HashTable采用头插法（效率高）

3. LinkedHashMap

   继承关系：

   • Map接口：键值对 key➡value 的形式保存，key不能重复
     • AbstractMap类
       • HashMap类
         • LinkedHashMap类（线程不安全）

   LinkedHashMap与HashMap主要区别：LinkedHashMap继承HashMap，拥有HashMap的特性，HashMap每次put元素时，由于哈希值无序，且为单链表，导致存放的位置是无序的，无法保证元素添加的先后顺序，LinkedHashMap通过额外维护一个双向链表，来保证元素添加的先后顺序，所以LinkedHashMap是有序的，但为此也增加了时间和空间的开销

4. HashSet

   继承关系：

   • Iterator 接口
     • Collection 接口
       • Set 接口:存储无序的、不可重复的元素(数学中的集合)
         • HashSet类（线程不安全）

   HashSet特点：无序，允许null值，线程不安全，存储不可重复的元素，内部采用了HashMap作为数据存储。HashSet其实就是在操作HashMap的key，只不过HashMap存键值对，HashSet存单值。

   常用方法：

   1、add(Object obj)：向Set集合中添加元素，添加成功返回true，否则返回false。

   2、size()：返回Set集合中的元素个数。

   3、remove(Object obj)： 删除Set集合中的元素，删除成功返回true，否则返回false。

   4、isEmpty()：如果Set不包含元素，则返回 true ，否则返回false。

   5、clear()： 移除此Set中的所有元素。

   6、iterator()：返回在此Set中的元素上进行迭代的迭代器。

   7、contains(Object o)：如果Set包含指定的元素，则返回 true，否则返回false。

5. LinkedHashSet

   继承关系：

   • Iterator 接口
     • Collection 接口
       • Set 接口:存储无序的、不可重复的元素(数学中的集合)
         • HashSet类
           • LinkedHashSet类

   LinkedHashSet与HashSet主要区别：LinkedHashSet继承HashSet，拥有HashSet的特性，底层使用LinkedHashMap存储元素，通过额外维护一个双向链表，来保证元素添加的先后顺序可知

常用集合小结：

List：存储有序可重复元素

• ArrayList:底层数组
• LinkedList：底层链表
• Vetcor：底层数组
  • Stack：底层数组

Queue：

• ArrayDueue：底层数组
• LinkedList：底层链表

Map：存储键值对（key-value），key不可重复，无序

• TreeMap：底层红黑树
• HashMap：底层数组+链表+红黑树
  • LinkedHashMap：底层数组+链表+红黑树
• HashTable：底层数组+链表

Set：存储无序（添加时无序）不可重复元素（内部由相应的Map容器存储，操作Map中的key，底层数据结构与相应Map容器相同，由于Map无序，所以Set也无序，由于Map的key不可重复，所以Set元素不可重复）

• TreeSet：基于TreeMap实现
• HashSet：基于HashMap实现
  • LinkedHashSet：基于LinkedHashMap实现

Tree—：可实现排序

Linked—：添加时可能无序，但能知道添加的顺序

以上除HashTable和Vetcor线程安全外，其他都线程不安全