JAVA

【JAVA】各バージョンによるHashMapのIndex割り当ての違い

JavaのバージョンによりHashMapのIndexを求める方法が異なっていたのでメモ

各バージョンによる処理の違い

各バージョンのHashMapはどのように処理をしているのかソースにて見比べることにしました。
・put、hashメソッド部分のみを抽出。

J2SE 1.4

インデックス番号の割り出し方法は
キー値からハッシュ値出力⇒ハッシュ値をビット演算⇒テーブルサイズでマスク
の順に行っています。

[java highlight="1,20,30"]
public Object put(Object key, Object value) {
Object k = maskNull(key);
int hash = hash(k);
int i = indexFor(hash, table.length);

    for (Entry e = table[i]; e != null; e = e.next) {
        if (e.hash == hash && eq(k, e.key)) {
            Object oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, k, value, i);
    return null;
}

static int hash(Object x) {
    int h = x.hashCode();

    h += ~(h << 9);
    h ^=  (h >>> 14);
    h +=  (h << 4);
    h ^=  (h >>> 10);
    return h;
}

static int indexFor(int h, int length) {
    return h & (length-1);
}

[/java]

 

J2SE 1.5

newHashメソッドとoldHashメソッドをどちらかを使うかによってハッシュ値の計算方法が変わります。
デフォルトはoldHashでJ2SE 1.4と同じ処理になります。
newHashにしたい場合は起動オプションにて-XX:+UseNewHashFunctionまたは-XX:+AggressiveOptsを追加すればよいとのこと。(42行目以降に記載)

[java highlight="1,21,25,30,38,42"]
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
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++;
    addEntry(hash, key, value, i);
    return null;
}

static int hash(int h) {
return useNewHash ? newHash(h) : oldHash(h);
}

private static int newHash(int h) {
    h ^= (h &gt;&gt;&gt; 20) ^ (h &gt;&gt;&gt; 12);
    return h ^ (h &gt;&gt;&gt; 7) ^ (h &gt;&gt;&gt; 4);
}

private static int oldHash(int h) {
    h += ~(h &lt;&lt; 9);
    h ^=  (h &gt;&gt;&gt; 14);
    h +=  (h &lt;&lt; 4);
    h ^=  (h &gt;&gt;&gt; 10);
    return h;
}

static int indexFor(int h, int length) {
    return h &amp; (length-1);
}

/**
 * Whether to prefer the old supplemental hash function, for
 * compatibility with broken applications that rely on the
 * internal hashing order.
 *
 * Set to true only by hotspot when invoked via
 * -XX:+UseNewHashFunction or -XX:+AggressiveOpts
 */
private static final boolean useNewHash;
static { useNewHash = false; }

[/java]


Eclipseの場合、VM引数オプションに追加することでnewHashメソッドで処理できるようになります。

Java SE 1.6

J2SE 1.5のnewHashのみになったみたいです。

[java highlight="1,21,26"]
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
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++;
    addEntry(hash, key, value, i);
    return null;
}

static int hash(int h) {
    h ^= (h &gt;&gt;&gt; 20) ^ (h &gt;&gt;&gt; 12);
    return h ^ (h &gt;&gt;&gt; 7) ^ (h &gt;&gt;&gt; 4);
}

static int indexFor(int h, int length) {
    return h &amp; (length-1);
}

[/java]

 

Java SE 1.7

hashSeedというハッシュの初期化値が0以外かつキー値がString型の場合は別処理にてハッシュ値を求めるようです。(デフォルト:0)
上記以外はJava SE 1.6と同じかと思いきやキー値のハッシュ値と0でXOR演算しているため若干処理が変わってるようです。

[java highlight="1,24,35"]
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
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++;
    addEntry(hash, key, value, i);
    return null;
}

final int hash(Object k) {
    int h = hashSeed;
    if (0 != h &amp;&amp; k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();
    h ^= (h &gt;&gt;&gt; 20) ^ (h &gt;&gt;&gt; 12);
    return h ^ (h &gt;&gt;&gt; 7) ^ (h &gt;&gt;&gt; 4);
}

static int indexFor(int h, int length) {
    return h &amp; (length-1);
}

[/java]

Java SE 1.8

処理の見直しがされたようで今までのとはかなり変わっています。

内容的にはハッシュコードが衝突した場合のパフォーマンス改善を行っているようです。

使ってあれこれキー値の検索をしているようです。

[java highlight="1,5"]
public V put(K arg0, V arg1) {
return this.putVal(hash(arg0), arg0, arg1, false, true);
}

final V putVal(int arg0, K arg1, V arg2, boolean arg3, boolean arg4) {
HashMap.Node[] arg5 = this.table;
int arg7;
if(this.table == null || (arg7 = arg5.length) == 0) {
arg7 = (arg5 = this.resize()).length;
}

  Object arg6;
  int arg8;
  if((arg6 = arg5[arg8 = arg7 - 1 &amp; arg0]) == null) {
     arg5[arg8] = this.newNode(arg0, arg1, arg2, (HashMap.Node)null);
  } else {
     Object arg9;
     label79: {
        Object arg10;
        if(((HashMap.Node)arg6).hash == arg0) {
           arg10 = ((HashMap.Node)arg6).key;
           if(((HashMap.Node)arg6).key == arg1 || arg1 != null &amp;&amp; arg1.equals(arg10)) {
              arg9 = arg6;
              break label79;
           }
        }

        if(arg6 instanceof HashMap.TreeNode) {
           arg9 = ((HashMap.TreeNode)arg6).putTreeVal(this, arg5, arg0, arg1, arg2);
        } else {
           int arg11 = 0;

           while(true) {
              arg9 = ((HashMap.Node)arg6).next;
              if(((HashMap.Node)arg6).next == null) {
                 ((HashMap.Node)arg6).next = this.newNode(arg0, arg1, arg2, (HashMap.Node)null);
                 if(arg11 &gt;= 7) {
                    this.treeifyBin(arg5, arg0);
                 }
                 break;
              }

              if(((HashMap.Node)arg9).hash == arg0) {
                 arg10 = ((HashMap.Node)arg9).key;
                 if(((HashMap.Node)arg9).key == arg1 || arg1 != null &amp;&amp; arg1.equals(arg10)) {
                    break;
                 }
              }

              arg6 = arg9;
              ++arg11;
           }
        }
     }

     if(arg9 != null) {
        Object arg12 = ((HashMap.Node)arg9).value;
        if(!arg3 || arg12 == null) {
           ((HashMap.Node)arg9).value = arg2;
        }

        this.afterNodeAccess((HashMap.Node)arg9);
        return arg12;
     }
  }

  ++this.modCount;
  if(++this.size &gt; this.threshold) {
     this.resize();
  }

  this.afterNodeInsertion(arg4);
  return null;

}
[/java]

テスト

[java title="テストソース"]
import java.util.HashMap;
import java.util.Iterator;

public class HashMapTest {
public static void main(String args[]){
HashMap testMap = new HashMap();
testMap.put("aaa", "111");
testMap.put("bbb", "222");
testMap.put("ccc", "333");
testMap.put("ddd", "444");
testMap.put("eee", "555");
testMap.put("fff", "666");
testMap.put("ggg", "777");
testMap.put("hhh", "888");

    for(Iterator iterator = testMap.keySet().iterator(); iterator.hasNext();){
        String key = (String) iterator.next();
        String value = (String) testMap.get(key);
        System.out.println(key+&quot;:&quot;+value);
    }
}

}
[/java]

1.4~1.8のバージョンを上記ソースで行っています。(1.4に合わせたソースになってます。)
実行結果(コンソール出力)とHashMap内の配列状況をまとめました。

結果

配列はEclipseのデバックモードにてtestMap.tableで取得した値です。
()内は同じIndex番号に入っている値です。

J2SE 1.5はnewは起動オプション(-XX:+UseNewHashFunction)を設定しています。

  実行結果 配列
1.4 fff:666
ccc:333
aaa:111
ggg:777
eee:555
ddd:444
bbb:222
hhh:888
[hhh=888, null, null, null, null, null, bbb=222, ddd=444, ggg=777(eee=555), null, null, aaa=111, ccc=333, null, fff=666, null]
1.5
(old)
fff:666
ccc:333
aaa:111
ggg:777
eee:555
ddd:444
bbb:222
hhh:888
[hhh=888, null, null, null, null, null, bbb=222, ddd=444, ggg=777(eee=555), null, null, aaa=111, ccc=333, null, fff=666, null]
1.5
(new)
eee:555
bbb:222
ccc:333
ggg:777
ddd:444
aaa:111
fff:666
hhh:888
[hhh=888, null, fff=666, aaa=111, ddd=444, null, null, null, null, ggg=777, ccc=333, null, null, null, bbb=222, eee=555]
1.6 hhh:888
fff:666
aaa:111
ddd:444
ggg:777
ccc:333
bbb:222
eee:555
[hhh=888, null, fff=666, aaa=111, ddd=444, null, null, null, null, ggg=777, ccc=333, null, null, null, bbb=222, eee=555]
1.7 hhh:888
fff:666
aaa:111
ddd:444
ggg:777
ccc:333
bbb:222
eee:555
[hhh=888, null, fff=666, aaa=111, ddd=444, null, null, null, null, ggg=777, ccc=333, null, null, null, bbb=222, eee=555]
1.8 aaa:111
ccc:333
bbb:222
eee:555
ddd:444
ggg:777
fff:666
hhh:888
[aaa=111, null, ccc=333, bbb=222, eee=555, ddd=444, ggg=777, fff=666, null, hhh=888, null, null, null, null, null, null]

各バージョン取得する順序はバラバラですね。Java SE1.6と1.7が同じ値だったのは意外でした。

また、J2SEとJavaSEで値を取得する順序も違うっていうのは面白いですね。
KeySetで確認しても同じでしたのでIteratorの違いというよりKeySetクラスの仕様が変わったのかな。

まとめ

HashMapは結構手を入れらてるんですね。各バージョンによって同じ値を入れた場合でも取得順は異なるということがわかりました。

JAVAのバージョンアップを行う際は注意したほうがよさそうですね。
(順序保証されていないので順番に取得しようとしてるのはどうかと思いますが。)

-JAVA
-,

© 2020 かえでBlog