Hash表也叫散列表,是一张非常重要的数据结构,很多缓存技术的核心就是在内存中维护一张大的Hash表
简单回顾其他数据结构在增删改查时的时间复杂度(空间复杂度暂不分析)
为什么算法复杂度中O(logN)中没有明确底数, 它的底数究竟是多少?
解惑: 算法中的log级别的时间复杂度 由于采用了分治思想,这个底数直接由分治的复杂度决定. 比如采用二分法,那么就是以2为底数, 三分法就是以3为底数. 不过无论底数是什么,log级别的渐进意义都是一样的.也就是说该算法的时间复杂度的增长与处理数据的增长关系是一样的
算法思想
- 贪心算法
- 分治算法(分解为K个规模较小的子问题)
- 动态规划(阶段规划 分组规划)
- 穷举搜索
数据结构
- 动态数组
- 数组栈
- 数组队列
- 循环数组
- 循环数组队列(数组和链表)
- 链表
- 链表栈
- 链表队列
- 双链表
- 循环列表
- 数据链表
- 集合
- 映射
- 优先队列
- 最大堆
- 线段树
- Trie前缀树
- 并查集
- AVL树
- 2-3树
- 红黑树
- 哈希表
简单解释一下几种:
==数组:== (采用了一段连续的存储单元来存储数据)
- 插入和删除: 涉及数组的元素移动, 其平均复杂度也是O(n)
- 查找 和 改: 已知索引O(1) , 未知索引O(n)
- 定值查找 : 需要遍历数组, 逐一对比, 时间复杂度是O(n)
- 对于有序数组,可以采用二分查找,插值插值,斐波那契查找,可以将时间复杂度提高到O(log n)
==线性链表:==
- 对于链表的新增,删除等操作, 找到指定操作位置之后(比如链表头), 仅需要处理结点间的引用即可, 时间复杂度是O(1)
- 其他增删改查,需要遍历列表逐一比对, 时间复杂度都是O(n)
==二叉树:==
- 找一颗相对平衡的有序二叉树,对其进行插入 查找 删除等操作,平均时间复杂度为O(log n)
==哈希表:(数组和链表为底层结构)==
- 相对于其他几种数据结构, 性能十分之高, 不考虑哈希冲突的情况下,仅需要一次定位完成 时间复杂度O(1)
==链地址法解决哈希冲突时, 总共有M个地址,如果放入哈希表的元素为N:==
- 每个地址用链表实现: 时间复杂度0(N/M)
- 每个地址用平衡树实现: 时间复杂度O( log(N/M) )
==动态空间的哈希表: 均摊复杂度为O(1)==
正式介绍哈希表
我们知道，数据结构的物理存储结构只有两种：==顺序存储结构==和==链式存储结构==（像栈，队列，树，图等是从逻辑结构去抽象的，映射到内存中，也这两种物理组织形式），而在上面我们提到过，在数组中根据下标查找某个元素，一次定位就可以达到，哈希表利用了这种特性，==哈希表的主干就是数组==。
比如我们要新增或查找某个元素,我们通过把当前元素的关键字
通过某个函数映射到数组中的某个位置，通过数组下标一次定位就可完成操作。
存储位置 = f(关键字)
通过f函数计算出事迹存储位置, 然后从数组中取出对应地址即可
这个f函数就是哈希函数 , 这个函数设计的好坏会直接影响哈希表的性能
哈希冲突:
然而万事无完美，如果两个不同的元素，通过哈希函数得出的实际存储地址相同怎么办？
也就是说，当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，
发现已经被其他元素占用了，其实这就是所谓的哈希冲突,，也叫哈希碰撞。
好的哈希函数会尽可能地保证 计算简单和散列地址分布均匀,
但是，我们需要清楚的是，数组是一块连续的固定长度的内存空间，
再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。
那么哈希冲突如何解决呢？
哈希冲突的解决方案有多种
1:开放定址法（发生冲突，继续寻找下一块未被占用的存储地址）
2:再散列函数法(再散列，多重散列,直到冲突不再发生为止。增加了计算时间。 )
3:链地址法(HashMap即是采用了链地址法，也就是数组+链表的方式),储存顺序是放在表头
4:建立一个公共溢出区,将哈希表分为基础表和溢出表两部分,凡是和基础表发生冲突的元素,一律填入溢出表.查找时,对给定key通过hash函数计算出散列位置,咸鱼基本表相应位置比对,如果相等 ,则查找成功,如果不相等,则去一处表进行顺序查找
HashMap的实现原理
HashMap的主干是一个Entry数组.每一个Entry包含一个key-value键值对
//HashMap的主干数组，可以看到就是一个Entry数组，初始值为空数组{}
//主干数组的长度一定是2的次幂，至于为什么这么做，后面会有详细分析。
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
Entry是HashMap的一个静态内部类
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;//存储指向下一个Entry的引用，单链表结构
int hash;//对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
==简单来说，HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。==
==在JDK1.6，JDK1.7中，HashMap采用位桶+链表实现，即使用链表处理冲突,同一hash值的键值对会被放在同一个位桶里，当桶中元素较多时，通过key值查找的效率较低。==
==而JDK1.8中，HashMap采用位桶+链表+红黑树实现，当链表长度超过阈值（8）,时，将链表转换为红黑树，这样大大减少了查找时间。==
//实际存储的key-value键值对的个数
transient int size;
//阈值，当table == {}时，该值为初始容量（初始容量默认为16）；
//当table被填充了，也就是为table分配内存空间后，threshold一般为 capacity*loadFactory。
//HashMap在进行扩容时需要参考threshold，后面会详细谈到
int threshold;
//负载因子，代表了table的填充度有多少，默认是0.75
final float loadFactor;
//用于快速失败，由于HashMap非线程安全，在对HashMap进行迭代时，
//如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），
//需要抛出异常ConcurrentModificationException
transient int modCount;
HashMap有4个构造器，其他构造器如果用户没有传入initialCapacity 和loadFactor这两个参数，
会使用默认值,initialCapacity默认为16，loadFactory默认为0.75
//在常规构造器中，没有为数组table分配内存空间
//（有一个入参为指定Map的构造器例外），
//而是在执行put操作的时候才真正构建table数组
//方法已过时 但是注释可以看看
public V put(K key, V value) {
//如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），入参为threshold，此时threshold为initialCapacity 默认是1<<4(24=16)
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//如果key为null，存储位置为table[0]或table[0]的冲突链上
if (key == null)
return putForNullKey(value);
int hash = hash(key);//对key的hashcode进一步计算，确保散列均匀
int i = indexFor(hash, table.length);//获取在table中的实际位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
//如果该对应数据已存在，执行覆盖操作。用新value替换旧value，并返回旧value
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;//保证并发访问时，若HashMap内部结构发生变化，快速响应失败
addEntry(hash, key, value, i);//新增一个entry
return null;
}
其他流程
inflateTable这个方法用于为主干数组table在内存中分配存储空间，通过roundUpToPowerOf2(toSize)可以确保capacity为大于或等于toSize的最接近toSize的二次幂，比如toSize=13,则capacity=16;to_size=16,capacity=16;to_size=17,capacity=32.
//摘录自Android API 27
//HashMap中 hash函数 //这是一个神奇的函数，用了很多的异或，移位等运算，
//对key的hashcode进一步进行计算以及二进制位的调整等
//来保证最终获取的存储位置尽量分布均匀
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//摘录自 Android API 27 Object类
public int hashCode() {
return identityHashCode(this);
}
static int identityHashCode(Object obj) {
int lockWord = obj.shadow$_monitor_;
final int lockWordStateMask = 0xC0000000; // Top 2 bits.
final int lockWordStateHash = 0x80000000; // Top 2 bits are value 2 (kStateHash).
final int lockWordHashMask = 0x0FFFFFFF; // Low 28 bits.
if ((lockWord & lockWordStateMask) == lockWordStateHash) {
return lockWord & lockWordHashMask;
}
//最后返回了一个natice方法
return identityHashCodeNative(obj);
}
@FastNative
private static native int identityHashCodeNative(Object obj);
//来源于 Android 8.0 系统级源码 java_lang_Object.cc
static jint Object_identityHashCodeNative(JNIEnv* env, jclass, jobject javaObject) {
ScopedFastNativeObjectAccess soa(env);
ObjPtr<mirror::Object> o = soa.Decode<mirror::Object>(javaObject);
return static_cast<jint>(o->IdentityHashCode());
}
==重写equals时也要同时覆盖hashcode的原因==
如果我们已经对HashMap的原理有了一定了解，这个结果就不难理解了。尽管我们在进行get和put操作的时候，使用的key从逻辑上讲是等值的（通过equals比较是相等的），但由于没有重写hashCode方法，所以put操作时，key(hashcode1)-->hash-->indexFor-->最终索引位置 ，而通过key取出value的时候 key(hashcode1)-->hash-->indexFor-->最终索引位置，由于hashcode1不等于hashcode2，导致没有定位到一个数组位置而返回逻辑上错误的值null（也有可能碰巧定位到一个数组位置，但是也会判断其entry的hash值是否相等，上面get方法中有提到。）
所以，在重写equals的方法的时候，必须注意重写hashCode方法，同时还要保证通过equals判断相等的两个对象，调用hashCode方法要返回同样的整数值。而如果equals判断不相等的两个对象，其hashCode可以相同（只不过会发生哈希冲突，应尽量避免）。
关于Hashmap初始大小为16 ,扩容因子0.75的解释
四种构造方法:
- HashMap（） 不带参数，默认初始化大小为16，加载因子为0.75
- HashMap（int initialCapacity） 指定初始化大小；
- HashMap（int initialCapacity ,float loadFactor）指定初始化大小和加载因子大小;
- HashMap(Map<? extends K,? extends V> m) 用现有的一个map来构造HashMap。
//构造方法 api 27
public HashMap(int initialCapacity, float loadFactor) {
//初始化大小小于0，抛出异常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//初始大小最大为默认最大值
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//加载因子(即扩容因子)要在0到1之间
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//threshold是根据当前的初始化大小和加载因子算出来的边界大小
//当桶中的键值对超过这个大小就进行扩容
//threshold=initialCapacity*loadFactor，桶中的键值对超过这个界限就把桶的容量变大。
this.threshold = tableSizeFor(initialCapacity);
}
//返回给定目标容量的两倍幂。(所以解释了, 为什么大小必须是2的倍数, 因为位移 计算机常用方式)
static final int tableSizeFor(int cap) {
//比如16是 10000 16-1 = 11111
//获取数组的推荐容量 (无符号右移)
//比如: 1011101
//与上: 1111111
//等于: 1011101
//特点不会改变数组的地址(原始是 hashcode 与上 2^n -1 ,这样保证了复制之后的数组和之前数组中 内容保持完全一致)
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
//如果超过当前位数 前面全部补0 等于没作用 其中8代表2^8
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
// put时候源码
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//添加时候都会验证 是否需要扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
// 扩容的核心代码 (不用细看 了解原理即可)
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
总结:我们可以知道这两个值主要影响的threshold的大小，这个值的数值是当前桶数组需不需要扩容的边界大小.我们都知道桶数组如果扩容，会申请内存空间，然后把原桶中的元素复制进新的桶数组中，这是一个比较耗时的过程。
如果桶初始化桶数组设置太大，就会浪费内存空间，16是一个折中的大小，既不会像1，2，3那样放几个元素就扩容，也不会像几千几万那样可以只会利用一点点空间从而造成大量的浪费。
加载因子设置为0.75而不是1，是因为设置过大，桶中键值对碰撞的几率就会越大，同一个桶位置可能会存放好几个value值，这样就会增加搜索的时间，性能下降，设置过小也不合适，如果是0.1，那么10个桶，threshold为1，你放两个键值对就要扩容，太浪费空间了。
所以说0.75只是一个预警值 , 是空间和时间的妥协产物.(泊松分布 ==8 时碰撞概率已经足够小了, 根据泊松分布公式 算出0.75(对照表))
常见哈希算法及其原理
==Hash的本质是用 唯一 少量 不可逆 的元素替代原始元素.==
==根据jvm源码分析得出:==
- 取模: 比如%8,这样大大减少了位数
- ^ 异或操作
- .>>> 2, 4或者 >>> 2,4: 左移位 或者 右移位操作
- 如果以上 仍然让你感觉不安全, 可以把以上几点 for循环几次
==理论上Hash是不可逆的(密码学常用) ,java这个还是能看到源码, 理论上可以破解 . 因为java在jvm中实现这个是提供给上层应用参考用, 如果需要加密请自己定规则或者用MD5之类的==
Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。==简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数==
哈希表是根据设定的哈希函数H（key）和处理冲突方法将一组关键字映射到一个有限的地址区间上，并以关键字在地址区间中的象作为记录在表中的存储位置，这种表称为哈希表或散列，所得存储位置称为哈希地址或散列地址。作为线性数据结构与表格和队列等相比，哈希表无疑是查找速度比较快的一种。
通过将单向数学函数（有时称为“哈希算法”）应用到任意数量的数据所得到的固定大小的结果。如果输入数据中有变化，则哈希也会发生变化。哈希可用于许多操作，包括身份验证和数字签名。也称为“消息摘要”。
简单解释：哈希（Hash）算法，即散列函数。它是一种单向密码体制，即它是一个从明文到密文的不可逆的映射，只有加密过程，没有解密过程。同时，哈希函数可以将任意长度的输入经过变化以后得到固定长度的输出。哈希函数的这种单向特征和输出数据长度固定的特征使得它可以生成消息或者数据。
==常见hash算法介绍:==
- MD4 : MD4（RFC 1320）是 MIT 的Ronald L. Rivest在 1990 年设计的，MD 是 Message Digest（消息摘要） 的缩写。它适用在32位字长的处理器上用高速软件实现——它是基于 32位操作数的位操作来实现的。
- MD5 : MD5（RFC 1321）是 Rivest 于1991年对MD4的改进版本。它对输入仍以512位分组，其输出是4个32位字的级联，与 MD4 相同。MD5比MD4来得复杂，并且速度较之要慢一点，但更安全，在抗分析和抗差分方面表现更好。
- SHA-1及其他: SHA1是由NIST NSA设计为同DSA一起使用的，它对长度小于264的输入，产生长度为160bit的散列值，因此抗穷举（brute-force）性更好。SHA-1 设计时基于和MD4相同原理，并且模仿了该算法。
待续
1.
1.
==一般来说 , Hash函数可以简单的分为以下几类:==
- 加法Hash
//所谓的加法Hash就是把输入元素一个一个的加起来构成最后的结果
static int additiveHash（String key， int prime）{
int hash， i;
for （hash = key.length（）， i = 0; i 《 key.length（）; i++）
hash += key.charAt（i）;
//这里的prime是任意的质数，看得出，结果的值域为［0，prime-1］
return （hash % prime）;
}
- 位运算Hash
//这类型Hash函数通过利用各种位运算（常见的是移位和异或）来充分的混合输入元素
static int rotatingHash（String key， int prime）{
int hash， i;
for （hash=key.length（）， i=0; i
hash = （hash<< 4 >>28）^ key.charAt（i）;
return （hash % prime）;
}
//先移位，然后再进行各种位运算是这种类型Hash函数的主要特点。
//比如，以上的那段计算hash的代码还可以有如下几种变形：
hash = (hash<<5>>27)^key.charAt(i);
hash += key.charAt(i);
hash += (hash << 10);
hash ^= (hash >> 6);
if((i&1) == 0) {
hash ^= (hash<<7>>3);
} else {
hash ^= ~((hash<<11>>5));
}
hash += (hash<<5> hash = key.charAt(i) + (hash<<6>>16) ? hash; hash ^= ((hash<<5>>2));
- 乘法Hash(平方hash)
static int bernstein(String key) {
int hash = 0; int i;
for (i=0; i return hash;}
// 32位FNV算法 int M_SHIFT = 0;
public int FNVHash(byte[] data) {
int hash = (int)2166136261L;
for(byte b : data)
hash = (hash * 16777619) ^ b;
if (M_SHIFT == 0)
return hash;
return (hash ^ (hash >> M_SHIFT)) & M_MASK;
}
- 除法Hash(除留余数法)
- 查表Hash
- 混合Hash
- 斐波那契Hash
==常用的构造散列函数的方法==
- 直接寻址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a?key + b，其中a和b为常数（这种散列函数叫做自身函数）
- 数字分析法：分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相 同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会 明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。
- 平方取中法：取关键字平方后的中间几位作为散列地址。
- 折叠法：将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。
- 随机数法：选择一随机函数，取关键字的随机值作为散列地址，通常用于关键字长度不同的场合。
- 除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p, p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。
==Hash算法在信息安全方面的应用主要体现在以下的3个方面：==
- ==文件校验== :我们比较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗数据篡改的能力，它们一定程度上能检测并纠正数据传输中的信道误码，但却不能防止对数据的恶意破坏。MD5 Hash算法的"数字指纹"特性，使它成为目前应用最广泛的一种文件完整性校验和(Checksum)算法，不少Unix系统有提供计算md5 checksum的命令。
- ==数字签名== :Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢，所以在数字签名协议中，单向散列函数扮演了一个重要的角色。 对 Hash 值，又称"数字摘要"进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点。
- ==鉴权协议== : 如下的鉴权协议又被称作挑战--认证模式：在传输信道是可被侦听，但不可被篡改的情况下，这是一种简单而安全的方法。
HashMap相关面试题
- HashMap与Hashtable的区别
- 继承父类不同 ,HashMap父类AvstractMap , Hashtable 父类 Dictionary
- 线程安全不同 HashMap非线程安全 Hashtable 线程安全
- HashMap 允许一个null键和n个null值 . HashTable不允许null键 null值
- 哈希值不同 Hashmap重新计算HashCode, HashTable直接使用对象的hashCode
- 遍历方式不同 HashMap使用Iterator ,HashTable使用Iterator和Enumeration
- 内部实现数组初始化和扩容方式不同 HashMap初始是16 扩容必须2倍(因为计算机位移操作) Hashtable扩容不要求必须是2的正数次幂,扩容是是变为原来的2倍加1
- 介绍HashMap
- 按照特点 HashMap 非线程安全 能接受一个null键n个null值, Hashtable线程安全 不接受null键 null值
- 按照工作原理 哈希值不同 扩容方式不同(详见上一题)
- HashMap的工作原理(不赘述)
- 两个HashCode相同时说明什么?
- hashcode相同 bucket(桶, 也就是数组)的位置相同, 会发生哈希碰撞,哈希表中的链表就会处理这种情况的, 会将元素存到LinkedList中,解决碰撞, 顺序存储是放在表头
- 如果两个键hashcode相同,如何获取值对象?
- 即找到bucket位置胡 通过key.equals()找到链表LinkedList中正确节点 ,返回要找的对象(使用不可变的 final的对象作为key, 并且采用equals()和hashCode(0方法, 将减少碰撞的发生,提供效率)
- HashMap大小超过负载因子定义的容量 怎么办?
- 自动扩容2倍(位移操作) 复制老数组到新数组中 这个过程叫rehashing
- 重新调整HashMap大小会出现什么问题?
- 多线程时候回出现条件竞争 可能形成死循环(因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历, 如果有条件竞争出现 , 那么妥妥的死循环了)
- HashMap在并发执行put操作 为什么会引起死循环?
- 因为多线程会导致hashmap的node链表形成环性链表,一旦形成环性链表, node的next节点永远不为空, 就会产生死循环获取node. 从而使CPU利用率接近100%
- 为什么String , Innterger这样的wrapper(包装)类适合做键?
- 因为他们是final 不可变的, 而且重写了equals()和hashcode()方法,避免了键值对改写(减少碰撞),提高HashMap性能
- 使用CocurrentHashMap代替Hashtable?
- 可以的 可使hashmap变成线程安全的
- Hashing的概念
- 散列法（Hashing）或哈希法是一种将字符组成的字符串转换为固定长度（一般是更短长度）的数值或索引值的方法，称为散列法，也叫哈希法。由于通过更短的哈希值比用原始值进行数据库搜索更快，这种方法一般用来在数据库中建立索引并进行搜索，同时还用在各种解密算法中。
- 扩展: 为什么equals方法要重写?
- 判断两个对象在逻辑上是否相等，如根据类的成员变量来判断两个类的实例是否相等，而继承Object中的equals方法只能判断两个引用变量是否是同一个对象。这样我们往往需要重写equals()方法。
- 我们向一个没有重复对象的集合中添加元素时，集合中存放的往往是对象，我们需要先判断集合中是否存在已知对象，这样就必须重写equals方法。
- 重写equals()的注意点
- 自反性:对于任何非空引用x，x.equals(x)应该返回true;
- 对称性：对于任何引用x和y，如果x.equals(y)返回true，那么y.equals(x)也应该返回true。
- 传递性：对于任何引用x、y和z，如果x.equals(y)返回true，y.equals(z)返回true，那么x.equals(z)也应该返回true。
- 一致性：如果x和y引用的对象没有发生变化，那么反复调用x.equals(y)应该返回同样的结果。
- 非空性：对于任意非空引用x，x.equals(null)应该返回false
