【数据结构】Set和Map_map的查找效率

Map和Set

1. 搜索

1.1 应用场景和概念

Map和set是一种专门用来进行搜索的容器或者数据结构，其搜索的效率与其具体的实例化子类有关。其应用场景在于 “数据重组” 和"数据存储", Set 是一种叫集合的数据结构, Map是一种叫字典的数据结构.

• 数据重组: 对重复数据或者特殊数据进行处理.
• 数据存储: 按照"键值对"的方式存储数据,方便快速查找.

1.2 模型

一般情况下把搜索的数据称为"关键字"(key), 而关键字对应的值称作"值"(value),而Map和Set分别对应两种模型:

• Set - > 纯Key模型

  • 查询字典中是否存在某个词.

• Map -> Key-Value模型

  • 每个人的身份证号码对应着单独自己的姓名.

2. Map

2.1 介绍

Map是一个接口,内部模型为Key-Value, 里面不能存放相同的key,每个key也只能对应一个value.而HashMap,TreeMap,Hashtable,SortedMap…实现了这个接口.

2.2 Map的遍历

Map没有继承Collection,但是Map.Entry<K, V> 是Map内部实现的用来存放<key, value>键值对映射关系的内部类，该内部类中主要提供了<key, value>的获取，value的设置以及Key的比较方式 .

注:Map.Entry<K,V>并没有提供设置Key的方法 .

1. 利用for - each中使用entry来遍历

Map<Integer, Integer> map = new HashMap<>();
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
    System.out.println("key" + entry.getKey() + "value" + entry.getValue());
}
1
2
3
4

注意：for-each循环在java 5中被引入所以该方法只能应用于java 5或更高的版本中。如果你遍历的是一个空的map对象，for-each循环将抛出NullPointerException，因此在遍历前你总是应该检查空引用。

2. 在for-each循环中遍历key或value。

   for (Integer key : map.keySet()) {
   System.out.println("key" + key);
   }
   for (Integer value : map.values()) {
   System.out.println("value" + value);
   }
   1
   2
   3
   4
   5
   6

   该方法比entrySet遍历在性能上稍好,而且代码更加干净。

3. 使用Iterator遍历

Iterator<Map.Entry<Integer, Integer>> entryIterator = map.entrySet().iterator();
while (entryIterator.hasNext()) {
Map.Entry<Integer, Integer> entry = entryIterator.next();
System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
}

1
2
3
4
5
6

4. 通过键找值遍历

for (Integer key : map.keySet()) {
Integer value = map.get(key);
System.out.println("Key = " + key + ", Value = " + value);
}
1
2
3
4

因为从键取值是耗时的操作,所以效率低.

2.3 Map的常用方法

注意事项:

1. Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap,HashMap,TreeMap,Hashtable,SortedMap…
2. Map中存放键值对的Key是唯一的，value是可以重复的, 如果插入key对应value有数据,则会替换它.
3. 在Map中插入键值对时，实现类为HasMap时key和value可以为null,如果为TreeMap时key不能为null,value可以为null(这是因为TreeMap底层数据结构为红黑树(下面会讲其基础版-二叉搜索树),根据key进行插入,如果为null,无法比较,自然会报错,这也是为什么里面的key是有序的).
4. Map中的Key可以全部分离出来，存储到Set中来进行访问(因为Key不能重复) ,
5. Map中的value可以全部分离出来，存储在Collection的任何一个子集合中(value可能有重复)
6. Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行重新插入
7. TreeMap和HashMap的区别 :

3. Set

3.1 介绍

Set是继承自Collection的接口类，并且Set中只存储了Key .

3.2 Set的常用方法

注意事项:

1. Set继承Collection接口,其实现类为HashSet,TreeSet,SortedSet…
2. Set只能存储Key,并且Key是唯一的,所以可以用于集合的去重.
3. Set的底层是使用Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的
4. .Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入
5. TreeSet和HashSet区别

4. 搜索树

4.1 概念

二叉搜索树又称二叉排序树,具有以下特性:

• 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
• 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
• 它的左右子树也分别为二叉搜索树

4.2 操作

4.2.1 查找

查找逻辑:

• 当前节点不为空(循环):
  • 如果当前节点key == 查找key,返回true.
  • 如果当前节点key > 查找key,向左子树查找
  • 如果当前节点key < 查找key,向右子树查找
• 循环退出,返回false

public boolean search(int key) {
    TreeNode cur = root;
    while (cur != null) {
        if (cur.key == key) {
            return true;
        } else if (cur.key < key) {
            cur = cur.right;
        } else {
            cur = cur.left;
        }
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

4.2.2 插入

插入逻辑:

• 根节点不为空

​ 根据查找的逻辑寻找插入位置(有相同元素,则不插入).

• 根节点为空
  • 直接插入到根节点,返回true.

public boolean insert(int key) {
    //如果为树为空
    if (root == null) {
        root = new TreeNode(key);
        return true;
    }
    TreeNode cur = root;
    TreeNode parent = null;

    //寻找插入位置,有相同元素不插入
    while (cur != null) {
        if (cur.key < key) {
            parent = cur;
            cur = cur.right;
        } else if (cur.key > key) {
            parent = cur;
            cur = cur.left;
        } else {
            return false;
        }
    }
    TreeNode node = new TreeNode(key);
    if (parent.key < key) {
        parent.right = node;
    } else {
        parent.left = node;
    }
    return true;
}
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

• 递归版

public TreeNode insertIntoBST(TreeNode root, int val) {
    if(root == null){
        return new TreeNode(val);
    }
    if(root.key < val){
        root.right = insertIntoBST(root.right,val);
    } else {
        root.left = insertIntoBST(root.left,val);
    }
    return root;
}
1
2
3
4
5
6
7
8
9
10
11

4.2.3 删除

设待删除结点为 cur, 待删除结点的双亲结点为 parent

1. cur.left == null

   1. cur 是 root，则 root = cur.right
      1. cur 不是 root，cur 是 parent.left，则 parent.left = cur.right
      1. cur 不是 root，cur 是 parent.right，则 parent.right = cur.right

2. cur.right == null

   1. cur 是 root，则 root = cur.left
   2. cur 不是 root，cur 是 parent.left，则 parent.left = cur.left
   3. cur 不是 root，cur 是 parent.right，则 parent.right = cur.left

3. cur.left != null && cur.right != null

​ 1. 需要使用替换法进行删除，即在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被

​ 删除节点中，再来处理该结点的删除问题

public boolean remove(int key) {
    TreeNode cur = root;
    TreeNode parent = null;
    //要删除元素首先要找到该元素
    while (cur != null) {
        if (cur.key < key) {
            parent = cur;
            cur = cur.right;
        } else if (cur.key > key) {
            parent = cur;
            cur = cur.left;
        } else {
            //删除节点
            removeNode(parent, cur);
            return true;
        }
    }
    return false;
}


private void removeNode(TreeNode parent, TreeNode cur) {
    if (cur.left == null) {
        if (cur == root) {
            root = cur.right;
        } else if (cur == parent.left) {
            parent.left = cur.right;
        } else if (cur == parent.right) {
            parent.right = cur.right;
        }
    } else if (cur.right == null) {
        //这里有个前提条件：cur.left != null
        if (cur == root) {
            root = cur.left;
        } else if (cur == parent.left) {
            parent.left = cur.left;
        } else if (cur == parent.right) {
            parent.right = cur.left;
        }
    } else {
        //此时cur的左右节点都不为空
        //需要用替换法：在它的右子树中寻找中序下的第一个结点，用它的值填补到被删除节点中，再来处理该结点的删除问题
        TreeNode targetParent = cur;
        TreeNode target = cur.right;
        while (target.left != null) {
            targetParent = target;
            target = target.left;
        }
        cur.key = target.key;
        if (target == targetParent.left) {
            targetParent.left = target.right;
        } else {
            targetParent.right = target.right;
        }
    }
}
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

4.3 实现

/**
 * Created with Intellij IDEA.
 * Description:
 * User: a
 * Date: 2022-06-29
 * Time: 22:27
 */
public class BinarySearchTree {
    static class TreeNode{
        public int key;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int key) {
            this.key = key;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "key=" + key +
                    '}';
        }
    }



    public TreeNode root;

    /**
     * 插入
     * @param key
     * @return
     */
    public boolean insert(int key) {
        //如果为树为空
        if (root == null) {
            root = new TreeNode(key);
            return true;
        }
        TreeNode cur = root;
        TreeNode parent = null;

        //寻找插入位置,有相同元素不插入
        while (cur != null) {
            if (cur.key < key) {
                parent = cur;
                cur = cur.right;
            } else if (cur.key > key) {
                parent = cur;
                cur = cur.left;
            } else {
                return false;
            }
        }
        TreeNode node = new TreeNode(key);
        if (parent.key < key) {
            parent.right = node;
        } else {
            parent.left = node;
        }
        return true;
    }

    /**
     * 查找元素
     * @param key
     * @return
     */
    public boolean search(int key) {
        TreeNode cur = root;
        while (cur != null) {
            if (cur.key == key) {
                return true;
            } else if (cur.key < key) {
                cur = cur.right;
            } else {
                cur = cur.left;
            }
        }
        return false;
    }

    /**
     * 删除节点
     * @param key
     * @return
     */
    public boolean remove(int key) {
        TreeNode cur = root;
        TreeNode parent = null;
        //要删除元素首先要找到该元素
        while (cur != null) {
            if (cur.key < key) {
                parent = cur;
                cur = cur.right;
            } else if (cur.key > key) {
                parent = cur;
                cur = cur.left;
            } else {
                //删除节点
                removeNode(parent, cur);
                return true;
            }
        }
        return false;
    }

    private void removeNode(TreeNode parent, TreeNode cur) {
        if (cur.left == null) {
            if (cur == root) {
                root = cur.right;
            } else if (cur == parent.left) {
                parent.left = cur.right;
            } else if (cur == parent.right) {
                parent.right = cur.right;
            }
        } else if (cur.right == null) {
            //这里有个前提条件：cur.left != null
            if (cur == root) {
                root = cur.left;
            } else if (cur == parent.left) {
                parent.left = cur.left;
            } else if (cur == parent.right) {
                parent.right = cur.left;
            }
        } else {
            //此时cur的左右节点都不为空
            //需要用替换法：在它的右子树中寻找中序下的第一个结点，用它的值填补到被删除节点中，再来处理该结点的删除问题
            TreeNode targetParent = cur;
            TreeNode target = cur.right;
            while (target.left != null) {
                targetParent = target;
                target = target.left;
            }
            cur.key = target.key;
            if (target == targetParent.left) {
                targetParent.left = target.right;
            } else {
                targetParent.right = target.right;
            }
        }
    }

    public void inorder(TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        System.out.print(root.key + " ");
        inorder(root.right);
    }

    public TreeNode getRoot() {
        return root;
    }
}

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158

4.4 效率分析

二叉搜索树的查找和删除操作都先要查找,所以二叉搜索树的查找效率代表它各个操作的性能.对于一颗有n个节点的二叉搜索树,若没有元素的查找概率相同,那二叉搜索树的平均查找长度是二叉搜索树的深度.

然而对于元素的插入次序不同,得到的树结构也不同.

• 最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：logN

• 最差情况下，二叉搜索树退化为单支树，其平均比较次数为 : N/2

如果退化成单支树，二叉搜索树的性能就失去了,于是在Java中的TreeMap 和 TreeSet 中利用红黑树实现的 Map 和 Set,而红黑树是一颗近似平衡的二叉搜索树,在二叉搜索树的基础之上 + 颜色以及红黑树性质验证.

5. 哈希表

5.1 概念

在顺序结构和树结构中,在该结构中查找需要经过关键码的多次比较,在顺序结构中查找时间复杂度为0(N),平衡树的为0(logN),即树的高度.那有没有一种结构可以不用经过任何比较,直接从表中获得要搜索的元素.哈希表就能够做到,具体思想是通过某种函数(hashFunc)使元素的存储位置与它的关键码(由函数生成的)之间建立一一对应的关系,那么就可以达到0(1)的时间复杂度.

引入概念:

1. 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表.
2. 若关键字为k,那么通过散列函数f(k)得到的结果就确定它存放的地址.按照这个思想建立的表为散列表.

5.2 散列函数

散列函数可以使对数据的查找更加迅速,那么在生产环境中,需要考虑的因素有:

1. 对于关键字集合中的每一个元素,经散列函数映象到地址集合中任何一个地址的概率是相等的,这就是使关键字经过散列函数得到一个随机地址,从而减少冲突.
2. 散列函数的定义域必须包括需要存储的全部关键码,即散列表有m个地址时,其值域必须在0~m-1之间.
3. 计算哈希函数所需的时间不应该太长.
4. 哈希表的大小.
5. 哈希函数应该简单,以提高地址运算的速度.

常见的哈希函数:

1. 直接寻址法

取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b,其中a和b为常数,若其中H(key)中已经有值了，就往下一个找，直到H(key)中没有值了，就放进去. 这种方法需要事先知道关键字的分布情况 ,适合查找比较小且连续的情况

2. 除留余数法

设散列表中允许的地址数为m**，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：**Hash(key) = key% p(p<=m),将关键码转换成哈希地址 .

3. 平方取中法

当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址.平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

4. 折叠法

将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

5. 随机数法

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数 .通常用于关键字长度不等的场合。

6. 数字分析法

设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。例如 :

假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是 相同的，那么我们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现 冲突，还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方法。

数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况

注：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

5.3 冲突

5.3.1 概念

对于两个数据元素的ki关键字kj和 (i != j)，有ki != kj，但有：Hash( ki) == Hash( kj)，即不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为**“同义词”**。

首先，我们需要明确一点，由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的，这就导致一个问题，冲突的发生是必然的，但我们能做的应该是尽量的降低冲突率

5.3.2 负载因子

负载因子和冲突率的关系图示:

所以当冲突率不断上升时,我们必须要降低负载因子,又因为在负载因子的定义中可以知道,表中元素个数是不可变,所以只能改变散列表的大小来降低负载因子.

5.3.3 解决方法

解决哈希冲突两种常见的方法是：闭散列和开散列

5.3.3.1 闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去 .

在上面的场景中如果再插入44,通过哈希函数计算的下标为4,此时就产生哈希冲突.此时有两种解决方案:

1. 线性探测

思想:从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

探测步骤:

• 通过哈希函数得到关键字的在哈希表中地址
• 检查该地址是否被占用,没有占用直接插入,占用就向后遍历,找到空位置插入.
• 采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

2. 二次探测

线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为$H_i=(H_0+i^2)\%m$,或者$H_i=(H_0-i^2)\%m$其中：i = 1,2,3…， 是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小.

研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容 .

总结:对于它的缺陷是空间利用率高,但这是哈希表的缺陷,这种方法在查找或者删除(二者其实一样,你要先查找,然后才能删除)时,如果哈希表中元素密集,在查找时(与负载因子有关)最坏的时间复杂度为0(N),效率低下.

5.3.3.2 开散列

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中 .

5.3.3.3 平均查找长度

已知有一个关键字序列：（19,14,23,1,68,20,84,27,25,11,10,79）散列存储在一个哈希表中，若散列函数为H(key)=key%7，并采用链地址法来解决冲突，则在等概率情况下查找成功的平均查找长度为()

14,1,23,10,11,19,20: 比较1次就可以找到; 84,79,68,27:需要比较两次才可以找到; 25: 需要比较三次才可以找到.

总的比较次数为：7+4*2+3=18，总共有12个元素

等概率情况下查找成功的平均查找长度为：18/12 = 1.5

5.4 模拟实现

  import java.util.NoSuchElementException;

/**
 * Created with Intellij IDEA.
 * Description:
 * User: a
 * Date: 2022-07-02
 * Time: 20:39
 */
public class HashBuck {
    static class Node {
        public int key;
        public int val;
        public Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    public Node[] array;
    public int usedSize;//存放的元素个数
    private static final double DEFAULT_LOAD_FACTOR = 0.75;//默认负债因子

    public HashBuck() {
        //默认大小为8
        array = new Node[8];
    }

    /**
     * 存放元素
     * @param key
     * @param val
     */
    public void put(int key, int val) {
        Node node = new Node(key, val);
        //根据哈希函数找到目标下标
        int index = key % array.length;

        //1.遍历当前下标下的链表是否存在该val
        Node cur = array[index];
        while (cur != null) {
            if (cur.key == key) {
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        //2.没有找到，只能插入当前链表
        //采用头插法：
        node.next = array[index];
        array[index] = node;
        usedSize++;
        if (loadFactor() >= DEFAULT_LOAD_FACTOR) {
            resize();
        }

    }

    /**
     * 扩容
     * 要进行重新哈希，即遍历每一个结点
     */
    private void resize() {
        Node[] tmp = new Node[2 * array.length];
        //遍历原来的数组
        for (int i = 0; i < array.length; i++) {
            //得到当前下标的链表头
            Node cur = array[i];
            while (cur != null) {
                Node curNext = cur.next;
                //重新计算下标
                int index = cur.key % tmp.length;
                //插入
                cur.next = tmp[index];
                tmp[index] = cur;
                //更新结点
                cur = curNext;
            }
        }
        array = tmp;
    }

    private double loadFactor() {
        return (double)usedSize / array.length;
    }
    /**
     * 获取元素
     * @param key
     * @return
     */
    public int get(int key) {
        int index = key % array.length;
        Node cur = array[index];
        while (cur != null) {
            if (cur.key == key) {
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
    }

    /**
     * 是否存在key
     * @param key
     * @return
     */
    public boolean containsKey(int key) {
        int index = key % array.length;
        Node cur = array[index];
        while (cur != null) {
            if (cur.key == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    /**
     * 是否存在value
     * @param value
     * @return
     */
    public boolean containsValue(int value) {
        for (int i = 0; i < usedSize; i++) {
            for (Node cur = array[i]; cur != null; cur = cur.next) {
                if (cur.val == value) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 删除key
     * @param key
     * @return
     */
    public int remove(int key) {
        int index = key % array.length;
        //1. 判断链表头是否为删除元素
        Node head = array[index];
        if (head.key == key) {
            int val = head.val;
            array[index] = head.next;
            //删除该节点
            head.next = head = null;
            usedSize--;
            return val;
        }
        //2.链表头不是
        Node pre = head;
        while (pre.next != null) {
            if (pre.next.key == key) {
                // pre为删除元素的前驱
                Node cur = pre.next;
                int val = cur.val;
                //删除
                pre.next = cur.next;
                cur.next = cur = null;
                usedSize--;
                return val;
            }
        }
        throw new NoSuchElementException("不存在");
    }
}

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171

5.5 性能分析

在实际使用过程中，我们认为哈希表的冲突率是不高的，冲突个数是可控的，也就是每个桶中的链表的长度是一个常数，所以，通常意义下，我们认为哈希表的插入/删除/查找时间复杂度是O(1) 。

5.6 Java中的Map和Set

1. Set是Map的子类,

其实Set就是利用Map中key的不可重复性,value传个空对象就行了.

2. 在JDK7之前HashMap是一个基于开开散列的散列表实现：数组+链表结构。
3. JDK8之后引入了红黑树：数组+链表（或红黑树），当冲突不严重就是链表，冲突严重就是红黑树。

当通过哈希函数计算的地址大部分相同时,这时候哈希表就会趋于链表化,此时查找的时间复杂度为0(N),所以在JDK8引入了在链表元素大于64并且链表长度大于8时,就会树化,最差也是$lo{g}_{2}N$

源码分析:

1. 静态变量分析

2. 插入元素分析

3. 构造方法传入默认容量代码

如果容量为0，则容量为0，在第一次put后，大小变为16

4. hashCode()与equals()

哈希码产生依据：哈希码并不是完全唯一的，它是一种算法，让同一个类的对象按照自己不同的特征尽量的有不同的哈希码，但不表示不同的对象哈希码完全不同。也有相同的情况。

Q1:hashCode()方法和equal()方法的作用其实一样，在Java里都是用来对比两个对象是否相等一致，那么equal()既然已经能实现对比的功能了，为什么还要hashCode()呢？

• 因为重写的equal()里一般比较的比较全面比较复杂，这样效率就比较低，而利用hashCode()进行对比，则只要生成一个hash值进行比较就可以了，效率很高，那么hashCode()既然效率这么高为什么还要equal()呢？
  • 因为hashCode()并不是完全可靠，有时候不同的对象他们生成的hashcode也会一样（生成hash值得公式可能存在的问题），所以hashCode()只能说是大部分时候可靠，并不是绝对可靠，所以我们可以得出：
    • 1. equal()相等的两个对象他们的hashCode()肯定相等，也就是用equal()对比是绝对可靠的。
      2. hashCode()相等的两个对象他们的equal()不一定相等，也就是hashCode()不是绝对可靠的。