week08_day01_MyHashMap
符号表(Map)概述
符号表在java中就是Map接口，说白了就是映射
我们使用符号表这个词来描述一张抽象的表格，我们会将信息(值)存储在其中，然后按照指定的键来搜索并获取这些信息。
符号表有时也被称为字典。键就是单词，值就是单词对应的定义，发音和词源。
符号表有时又叫做索引。键就是术语，值就是书中该术语出现的所有页码。
符号表的应用：
····················································································································································································································
哈希表概述
如果所有的键都是小整数，我们可以用一个数组来实现的符号表，将键作为数组的索引，而数组中对应的位置存储键关联的值。
小：如果键值很大，就需要创建很大空间的数组
整数：不能是String类型或者Student类型，因为数组下标只能是整数。
哈希表是这种简单方法的扩展，并且能够处理更加复杂类型的键。我们需要用哈希函数将键转换成数组的索引。
哈希表的核心算法可以分为两步。
-
用哈希函数将键转换为数组中的一个索引。理想情况下不同的键都能转换成不同的索引值。当然这只是理想情况下，所以我们需要处理两个或者多个键都散列到相同索引值的情况 (哈希碰撞)。
-
处理碰撞冲突。
a. 开放地址法
线性探测法, 平方探测法, 再散列法…
b. 拉链法
哈希函数
一个优秀的 hash 算法，满足以下特点：
- 正向快速：给定明文和 hash 算法，在有限时间和有限资源内能计算出 hash 值。
正向快速是哈希函数本身的一个效率问题 - 逆向困难：给定（若干） hash 值，在有限时间内很难（基本不可能）逆推出明文。
- 输入敏感：原始输入信息修改一点信息（哪怕只有一比特不一样），产生的 hash 值看起来应该都有很大不同。
- 冲突避免：很难找到两段内容不同的明文，使得它们的 hash 值一致（发生冲突）。即对于任意两个不同的数据块，其hash值相同的可能性极小；对于一个给定的数据块，找到和它hash值相同的数据块极为困难。
我们可以简单地把哈希函数理解为在模拟随机映射，然后从随机映射的角度去理解哈希函数。
经典的哈希函数
MD4: 128位，MD4已被证明不够安全。
MD5：MD5 已被证明不具备"强抗碰撞性"。
SHA1：SHA-1 已被证明不具"强抗碰撞性"。
SHA2：
SHA3: 相关算法已经被提出。
哈希算法的应用
- 指纹 (身份的标识)
a. 证书, 文件
b. 加密
假如你去柜台，让银行小姐姐给查看一下你的银行卡密码，她也查不到，为啥子，因为银行数据库里存的是密码是你的密码明文经过哈希映射后的哈希值，而哈希函数逆向困难。
但是假如你输入的是一个错误密码，但这个错误密码和你正确密码的哈希值正好相同了（概率极小），那你也能登陆成功。
也就是说，密码D1的哈希值是hash1，而密码D2的哈希值也是hash1，输入密码D2也能登陆成功，因为数据库中存的就是你的哈希值，而不是明文。
所以，怎么算把一个密码**了呢？把一个哈希值对应的明文求出就算**了，管你密码是D1还是D2，我求出一个就能登上你的账号了。
而如果黑客盗取一个系统的数据库，他得到的其实是用户名和用户密码对应的哈希值，而你拿着哈希值是无法登陆系统的。
由于逆向推出密码明文十分困难，于是，黑客就整一个很大的Map，比如书MD5加密的Map，键是哈希值，值是明文。他就拿哈希值去这个Map库中去找，有没有对应的明文，这样的话，如果是HashMap的话，就能做到O(1)的时间复杂度，找到密码明文就很快。这就叫撞库攻击。
那如何防御撞库攻击呢？
- 不要取简单的密码，最好是数字和英文大小写组合。因为撞库攻击中，黑客的Map库肯定不全，你不可能一个库中把世界上所有的密码都包含了，所以用户设计的密码越复杂，黑客的库拥有你的密码的哈希值的可能性越小，越不容易被盗。
- 加盐。服务器端得到密码后，在密码尾部或前端加上某个字符串如：“abc”，得到新的密码后，再通过哈希算法得到哈希值，存在数据库中。黑客就算盗走了哈希值，他撞库攻击后得到的密码明文也是在原始密码后加“abc”的密码，并不知道加盐算法是啥，也就无法得到原始密码。
…
- 散列
a. 集群, 分布式
b. 数据结构（哈希表中的哈希函数）
…
假如京东有十台服务器，而618也快到了，有的服务器特别忙，有的服务器特别闲，怎么做到负载均衡呢？
因为哈希函数可以简单的理解为随机映射，就可以将任务随机的分配到每个服务器
注意事项：其实把hash算法当成是一种加密算法，这是不准确的，我们知道加密总是相对于解密而言的，没有解密何谈加密呢，HASH的设计以无法解密为目的的。并且如果我们不附加一个随机的salt值，HASH口令是很容易被字典攻击入侵的。
····················································································································································································································
哈希函数在数据结构中的应用
在数据结构中，对速度比较重视，对抗碰撞性（有多个值的哈希值是一样的，没关系，只要保证哈希值的平均分布即可）不太看重。所以对哈希函数的要求没那么高，
只要满足下面两点就可以了。
- 计算速度快。
- Hash值平均分布。
处理碰撞冲突——拉链法
发生碰撞冲突的元素都存储在同一条链表中。
在哈希函数能保证平均分布的前提下，那么哈希表的性能就取决于链表的平均长度。
如果我们想在常数时间复杂度内, 完成哈希表的增删查操作，那么我们就得控制链表的平均长度不超过某个值。这个值我们称之为加载因子，也就是链表平均长度可以达到的最大值。
因此，当元素个数达到一定的数目的时候，我们就需要对数组进行扩容。
简化处理
-
键不能为null。如果键为null，我们会抛出 NullPointerException.
-
值不能为null。我们这么规定的原因是：当键不存在的时候，get()方法会返回null。这样做有个好处，我们可以调用get()方法，看其返回值是否为 null 来判断键是否存在哈希表中。
-
缓存hash值。如果散列值计算很耗时 (比如长字符串)。那么我么可以在结点中用一个 hash 变量来保存它计算的 hash 值。Java 中的 String 就是这样做的。
-
当数组达到最大值时，并且链表的平均长度达到了最大值。这种情况，我们就破坏加载因子的限制，直接添加元素。
自己实现的HashMap：
package com.cskaoyan;
/**
* @author shihao
* @create 2020-05-25 19:34
* <p>
* API:
* void put(K key, V value)
* V get(K key)
* void delete(K key)
* void clear()
* boolean contains(K key)
* boolean isEmpty()
* int size()
* Set<K> keys()
*/
public class MyHashMap<K, V> {
//常量
private static final int DEFAULT_ARRAY_SIZE = 16;
private static final int MAX_ARRAY_SIZE = 1 << 30; //2^30
private static final float DEFAULT_LOAD_FACTOR = 0.75F;
//属性
private Entry[] table;
private int size;
private float loadFactor;
private int threshold; //阈值，当size达到threshold时就需要扩容了
private static class Entry {
Object key;
Object value;
int hash;
Entry next;
public Entry(Object key, Object value, int hash, Entry next) {
this.key = key;
this.value = value;
this.hash = hash;
this.next = next;
}
@Override
public String toString() {
return key + "=" + value;
}
}
//构造方法
public MyHashMap() {
this(DEFAULT_ARRAY_SIZE, DEFAULT_LOAD_FACTOR);
}
public MyHashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public MyHashMap(int initialCapacity, float loadFactor) {
if (initialCapacity <= 0 || initialCapacity > MAX_ARRAY_SIZE) {
throw new IllegalArgumentException("initialCapacity = " + initialCapacity);
}
if (loadFactor < 0) {
throw new IllegalArgumentException("loadFactor =" + loadFactor);
}
//求大于等于initialCapacity最小2的幂次方
int capacity = calculateCapacity(initialCapacity);
table = new Entry[capacity];
this.loadFactor = loadFactor;
this.threshold = (int) (table.length * loadFactor);
}
private int calculateCapacity(int cap) {
int n = cap - 1;
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
return n + 1;
}
//方法
/**
* 通过键获取值
*
* @param key 键
* @return 键关联的值，如果键不存在返回null
*/
@SuppressWarnings("unchecked")
public V get(K key) {
if (key == null) {
throw new IllegalArgumentException("key cannot be null!");
}
int hash = hash(key);
int index = indexFor(hash, table.length);
//遍历链表，找到key关联值
for (Entry e = table[index]; e != null; e = e.next) {
if (hash == e.hash && (key == e.key || key.equals(e.key))) {
return (V) e.value;
}
}
//没有这样的key
return null;
}
/**
* 找哈希值hash所在table中的索引位置
*
* @param hash 哈希值
* @param length table的长度
* @return 索引值
*/
private int indexFor(int hash, int length) {
return hash & (length - 1);
}
/**
* 自定义的哈希函数
*
* @param key key
* @return 哈希值
*/
private int hash(K key) {
int h = key.hashCode();
return (h << 16) ^ (h >> 16);
}
/**
* 判断key是否在哈希表中存在
*
* @param key 键
* @return 如果存在返回true，否则返回false
*/
public boolean contains(K key) {
return get(key) != null;
}
}
····················································································································································································································
并发场景
HashMap 类不同步，在并发场景中可能会出现许多问题。比较经典的一个问题是：查找的时候可能会出现死循环。
Q1: HashMap 和 Hashtable 的区别？
Q2: Java 给我们提供了哪些并发安全的 Map？我们应该选择哪一个？
a. Hashtable
b. Collections.synchronizedMap(Map map)
c. ConcurrentHashMap
Q3: JDK8 对 HashMap 的改进。
如果某条链表的长度超过8， 把这条链表变成红黑树。
如果某条链表的长度低于6， 把红黑树变成链表。