Java配列からHashMapまでのアルゴリズムの詳細な紹介
- 黄舟オリジナル
- 2017-03-18 11:08:391619ブラウズ
1. 配列とは何ですか?
「すべてのデータ構造は配列の進化である」というような文をどの本で見たか忘れましたが、これはよく考えてみると当然のことです。なぜなら、コンピューターのメモリは実際には線形の記憶空間だからです。
Java サンプル コード:
int[] array = new int[5]
object ヘッダー情報と配列長情報を無視します。 JVM は実行時にヒープに 20 バイトのメモリ領域を割り当てます。
このようなデータの構造。配列の添字を使用してデータに簡単にアクセスできますが、検索時に 配列を走査する必要があり、平均時間計算量は O(n/2) です。
データの量が大きい場合、または検索操作が頻繁に行われる場合、このような走査操作はほとんど受け入れられません。では、どうすればより短時間で迅速にデータを見つけることができるでしょうか?
2. 二分検索
配列内の要素がすでにソートされている場合、自然な方法は二分検索を使用することです。
たとえば、長さ 1000 の整数配列があり、配列内の 整数 が小さい順に並べられている場合、この配列に 6000 があるかどうかを知りたいとします。次に、配列 [500] の数値が 6000 であるかどうかを確認します。配列 [500] の数値が 6000 より小さい場合は、配列 [750] の位置の数値を確認します。その後も同様です。最大10回まで結果を決定できます。
このアルゴリズムの時間計算量は O(logN) です。
しかし、ほとんどの場合、配列要素は順序付けされておらず、並べ替えに必要な時間計算量 O(NlogN) は、通常、走査に必要な時間をはるかに超えています。
ということで、問題は原点に戻ります。乱れたデータの中からデータを素早く見つけるにはどうすればよいでしょうか?
3. 無知な思考
私は初めてプログラミングを学んだ直後に「Programming Pearls」を見たのを今でも覚えていますが、その中に次のような記述がありました: 1970年代、マイク・レスクは電話会社のために電話番号検索機能を構築しましたたとえば、「LESK*」と入力します。M* に対応する数字キーは 5375*6* で、エラー照合率はわずか 0.2% で正しい電話番号またはオプションのリストを返すことができます。
どうやってやるの？
当時はデータ構造もアルゴリズムも全く理解していなかったので、当時の妄想の過程を復元するのは今でも非常に興味深いです。
1.足し算
すべての数字を足し(*キーは11)、5375*6*の合計は48です。ほとんどの入力の合計は 100 を超えません。これは、数万の電話番号が配列の最初の 100 の位置にクラスター化されることを意味するため、現実的ではありません。
2. 掛け算
すべての数値を掛けると、積は 381150 になります。これは実現可能に思えますが、問題があります。lesk、lsek、slke... の積は同じであり、各数字キーも 3 つの文字に対応しているため、反復される可能性が非常に高くなります。
3. 乗算の改善
①同じ文字でアルファベット順が異なる文字列は、この方法で競合を回避できます。最初に各数値にシリアル番号が乗算され、次に他の値が乗算されます。
素数の位置がまだ使用されている場合は、次に近い素数を検索し続けます...この時点で、問題は解決されたようです。
ユーザーが数字の文字列を入力すると、式に従って積が計算され、下付き文字の位置にある電話番号が返されます。間違っている場合は、ある素数で添字が付いた配列要素が空になるまで後続の素数を順番に検索し、最終的に見つかったすべての電話番号を返します。ほとんどの場合、電話番号は O(1) 時間の計算量で見つけることができます。
5、数组太大
唯一的问题是，按照上述思路建立的数组实在是太大了。一个姓名有10个字母，假如每一个字母对应的数字都是9，最后得到的积约是9的17次方。这意味着要建立9^17大小的数组，这是完全不可行的。
6、后来
即使不考虑数组过大因素，以我当时初学编程的水平，这样的程序也是没有能力写出来的。
我之所以还原这个思考的过程，是觉得独立思考的过程非常有趣也很有价值。想想，其实现有的算法都是当年那些大牛在实际工程中一步一步寻求解决方案而最终推导得到的。
因此，当在工程中碰到一些棘手的难题时，只要乐于思考分解问题并寻求每一个小问题解决方案，那么很多所谓的难题都是可以解决的。
后来看了《数据结构与算法分析.Java语言描述》，我才知道原来我的思路其实就是开放寻址法（Open Addressing）。
JDK的HashMap使用的则是分离链接法(separate chaining)。不同：增加了桶的概念来保存冲突的数据；进行求余运算来降低数组大小。
那么，就谈谈Java中的HashMap吧。
四、HashMap结构及算法详解
HashMap的本质依然是数组，而且是一个不定长的多维数组，近似于下图这样的结构：
1、简单介绍
HashMap中的数组保存链表的头节点。
保存数据：
计算key的hashCode，再与数组长度进行求余运算得到数组下标(链表头节点)。
如果该位置为空，生成一个新的链表节点并保存到该数组。
如果该位置非空，循环比对链表的每一个节点：已经存在key相同的节点，覆盖旧节点；不存在key相同的节点，将新节点作为链表的尾节点（注：查看JDK1.8中的源码，新节点总是加入到链表末尾，而不是如JDK1.6一般作为链表头节点）。
查找数据：
计算key的hashCode，再与数组长度进行求余运算得到数组下标(链表头节点)。如果链表不为空，先比对首节点，如果首节点key相同（hashCode相同且equals为true），直接返回首节点的value；首节点key不同则顺序遍历比对链表其它节点，返回key相同的节点的value（未找到key相同的节点则返回null）。
HashMap引入链表的目的就是为了解决上一节讨论过的重复冲突问题。
注意事项：
如果所有key的hashcode相同，假定均为0，则0%4 = 0，所有元素就会都保存到链表0，保存和查找每一个数据都需要遍历链表0。那么，此时的HashMap实质上已经退化成了链表，时间复杂度也从设计的O(1)上升到了O(n/2)。
为了尽可能地让HashMap的查找和保存的时间复杂度保持在O(1),就需要让元素均匀地分布在每一个链表，也就是每一个链表只保存一个元素。
那么影响因素有哪些？
一是key的hashcode不能重复，如果重复就肯定会有链表保存至少2个元素；
二是哈希函数设计，如果只是简单的求余，那么余数会有大量重复；
三是链表的大小，如果100个元素要分布在长度为10的数组，无论怎么计算都会导致其中有链表保存多个元素，最好的情况是每个链表保存10个；
下面分别详细介绍这三个因素的算法设计。
2、hashcode生成
这是String类的hashCode生成代码。
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}String类的value是char[]，char可以转换成UTF-8编码。譬如，’a’、’b’、’c’的UTF-8编码分别是97,98,99；“abc”根据上面的代码转换成公式就是：
h = 31 * 0 + 97 = 97； h = 31 * 97 + 98 = 3105； h = 31 * 3105 + 99 = 96354；
使用31作为乘数因子是因为它是一个比较合适大小的质数：如值过小，当参与计算hashcode的项数较少时会导致积过小；如为偶数，则相当于是左位移，当乘法溢出时会造成有规律的位信息丢失。而这两者都会导致重复率增加。
如果使用32作为乘数因子(相当于 << 5)，以字符串“abcabcabcabcabc”为例，它的hashcode的每一步计算结果如下图：
如上图所示，字符串末尾每3个字母就会产生一个重复的hashcode。这并不是一个巧合，即使换成其它的英文字母，也有很容易产生重复，而使用质数则会大大地减少重复可能性。有兴趣的可以参照上图去作一下左位移运算，会发现这并不是偶然。
《Effective Java》一书中详细描述了hashcode的生成规则和注意事项，有兴趣的可以去看看。
从源代码的hashCode()方法可知，String类对象保存了已经计算好的hashCode，如果已经调用过hashCode()方法，那么第二次调用时不会再重新生成，而是直接返回已经计算好的hashCode。
String对象总是会存放到String类私有维护的常量池中，不显式使用new关键字时，如果常量池中已经有value相同的对象，那么总是会返回已有对象的引用。因此，很多情况下生成hashCode这种比较昂贵的操作实际上并不需要执行。
3、哈希函数设计
现在，已经得到了重复率很低的hashCode，还有什么美中不足的地方吗？
扰动函数
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}下图还是以字符串“abcabcabcabcabc”为例，使用上面方法得到的运算过程和结果。
为什么要先无符号右位移16位，然后再执行异或运算？看看下图的二进制的与运算，你就会明白。
你会发现只要二进制数后4位不变，前面的二进制位无论如何变化都会出现相同的结果。为了防止出现这种高位变化而低位不变导致的运算结果相同的情况，因此需要将高位的变化也加入进来，而将整数的二进制位上半部与下半部进行异或操作就可以得到这个效果。
为什么要使用与运算？
因为哈希函数的计算公式就是hashCode % tableSize，当tableSize是2的n次方(n≥1)的时候，等价于hashCode & (tableSize – 1)。
扰动函数优化前：1954974080 % 16 = 1954974080 & (16 – 1) = 0
扰动函数优化后：1955003654 % 16 = 1955003654 & (16 – 1) = 6
这就是为什么需要增加扰动函数的原因。
源代码详解
代码解释之前需要补充说明一下，jdk1.8引入了红黑树来解决大量冲突时的查找效率，所以当一个链表中的数据大到一定规模的时候，链表会转换成红黑树。因此在jdk1.8中，HashMap的查找和保存数据的最大时间复杂度实际上就是红黑树的时间复杂度O(logN)。
以下是HashMap中的保存数据的方法源代码，相信经过以上的描述，已经非常容易看懂这一段代码。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; //HashMap数组
Node<K,V> p; //初始化需要保存的数据
int n; //数组容量
int i; //数组下标
/* 如果数组为空或0，初始化容量为16 */
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; //临时变量用于比较key
//如果头节点与新节点的key的hash值相同 且 key的值相等，e赋值为旧节点
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))){
e = p;
}
//如果头节点是一个红黑树节点，那么e将保存为树节点
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) {
//如果直到链表尾未找到相同key的节点，将新结点作为最后一个节点加入到链表
p.next = newNode(hash, key, value, null);
//如果链表节点数大于等于8-1，转换成红黑树；转换成红黑树的最小节点数是8
if (binCount >= TREEIFY_THRESHOLD - 1){
treeifyBin(tab, hash);
}
break;
}
//如果循环过程中发现新旧key的值相同，跳转：是否覆盖旧值
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){
break;
}
p = e;
}
}
//是否覆盖旧值
if (e != null) {
V oldValue = e.value;
//如果新值不为空且（允许修改旧值 或 旧值为空），覆盖旧节点的值
if (!onlyIfAbsent || oldValue == null){
e.value = value;
}
afterNodeAccess(e); //回调函数，这里是空函数，但在linkedHashMap中实现了此方法
return oldValue; //返回旧值
}
}
//用于比较判断是否在遍历集合过程中有其它线程修改集合，详情请网上搜索fail-fast快速失败机制
++modCount;
//当key数量大于允许容量时进行扩容。允许容量在HashMap中是数组长度 * 装填因子(默认0.75)
if (++size > threshold){
resize();
}
//回调函数，这里是空函数，但在linkedHashMap中实现了此方法
afterNodeInsertion(evict);
return null;
}简化后的伪代码
putval(key, value){
index = key.hashcode % tablesize;
if(null == table[index]){
table[index] = new node(key, value);
}else{
firstNode = table[index];
nextNode = firstNode.next;
while(nextNode.hasNextNode()){
//如果找到相同key的旧节点，覆盖旧节点
if(key == nextNode.key){
nextNode = new node(key, value);
break;
}
//如果到队列末尾依然没有找到相同key的旧节点，将新结点加入到最后一个节点的末尾
if(nextNode.next == null){
nextNode.next = new node(key, value);
break;
}
nextNode = nextNode.next;
}
}
}链表大小设计
代码注释中已经稍有提及，这里再分别展开讨论。
①容量选择
HashMap的初始容量是 1 << 4，也就是16。以后每次扩容都是size << 1，也就是扩容成原来容量的2倍。如此设计是因为 2^n-1(n≥1)的二进制表示总是为重复的1，方便进行求余运算。
《数据结构与算法分析.Java语言描述》一书中的建议是容量最好是质数，有助于降低冲突，但没有给出证明或实验数据。
质数虽然是神奇的数字，但个人感觉在这里并没有特别的用处。
根据公式index = hashCode % size可知，无论size是质数还是非质数，index的值区间都是0至(size-1)之间，似乎真正起决定作用的是hashCode的随机性要好。
这里先不下结论，待以后再写一个随机函数比较下质数和非质数重复率。
②装填因子
装填因子默认是0.75，也就是说如果数组容量为16，那么当key的数量大于12时，HashMap会进行扩容。
装填因子设计成0.75的目的是为了平衡时间和空间性能。过小会导致数组太过于稀疏，空间利用率不高；过大会导致冲突增大，时间复杂度会上升。
その他について
赤黒ツリーは JDK 1.8 で導入されました。赤黒ツリーのデータ構造、追加、削除、変更、時間計算量解析を簡単な言語で明確に説明するのは複雑で困難な作業です。それ自体を説明したほうが良いので、それについては後ほど残しておきます。
5. Minimal Perfect Hash Function (MPHF)
Jdk の HashMap は、あらゆる データセット の時間計算量の問題を解決します。
しかし、既知のデータセット (Java キーワードセットなど) がある場合、次の 2 つの要件を同時に満たすハッシュ関数を設計する方法は次のとおりです。
⑴ コンテナーの容量は、コンテナーのサイズとまったく同じです。データセット
⑵ 競合はありません。
つまり、特定のデータセットが与えられたとき、ハッシュ関数がコンテナーの各ノードが 1 つのデータ要素を持つことを許可する場合、そのようなハッシュ関数は最小完全ハッシュ関数と呼ばれます。
最近、私はコンパイルの原理を勉強していて、キーワードセットのO(1)時間計算量検索問題を解く方法について言及し、最小の完全ハッシュ関数が使用できることについて言及しました。このような言葉を見ると、すぐにとても良い気持ちになり、崇高な気持ちになります。
以上がJava配列からHashMapまでのアルゴリズムの詳細な紹介の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。