ハッシュテーブルの仕組みと実装

基本構造の構築

ハッシュ値の生成手法は一旦置き、ハッシュ値が外部から与えられる前提でハッシュテーブルの骨組みを実装する。内部では配列と連結リストを用いてキーと値のペアを管理する。

public class CustomHashMap {

    static class Node {
        int code;
        Object key;
        Object val;
        Node next;

        Node(int code, Object key, Object val) {
            this.code = code;
            this.key = key;
            this.val = val;
        }
    }

    Node[] buckets = new Node[16];
    int count = 0;
    final double loadFactor = 0.75;
    int limit = (int) (loadFactor * buckets.length);

    // 配列のサイズが2の累乗である場合、剰余演算をビット演算に置き換え可能
    // hash % capacity == hash & (capacity - 1)

    public Object getValue(int code, Object key) {
        int pos = code & (buckets.length - 1);
        Node curr = buckets[pos];
        while (curr != null) {
            if (curr.key.equals(key)) {
                return curr.val;
            }
            curr = curr.next;
        }
        return null;
    }

    public void insert(int code, Object key, Object val) {
        int pos = code & (buckets.length - 1);
        if (buckets[pos] == null) {
            buckets[pos] = new Node(code, key, val);
        } else {
            Node curr = buckets[pos];
            while (true) {
                if (curr.key.equals(key)) {
                    curr.val = val; // 既存キーの更新
                    return;
                }
                if (curr.next == null) break;
                curr = curr.next;
            }
            curr.next = new Node(code, key, val); // 新規ノード追加
        }
        count++;
        if (count > limit) {
            expand();
        }
    }

    private void expand() {
        Node[] newBuckets = new Node[buckets.length << 1];
        for (int i = 0; i < buckets.length; i++) {
            Node curr = buckets[i];
            if (curr != null) {
                // 連結リストを2つに分割する最適化ロジック
                // code & oldCapacity == 0 のグループとそうでないグループに分かれる
                Node loHead = null, loTail = null;
                Node hiHead = null, hiTail = null;

                while (curr != null) {
                    if ((curr.code & buckets.length) == 0) {
                        if (loTail == null) loHead = curr;
                        else loTail.next = curr;
                        loTail = curr;
                    } else {
                        if (hiTail == null) hiHead = curr;
                        else hiTail.next = curr;
                        hiTail = curr;
                    }
                    curr = curr.next;
                }

                // loリストは元のインデックス、hiリストは元のインデックス+oldCapacityに配置
                if (loTail != null) {
                    loTail.next = null;
                    newBuckets[i] = loHead;
                }
                if (hiTail != null) {
                    hiTail.next = null;
                    newBuckets[i + buckets.length] = hiHead;
                }
            }
        }
        buckets = newBuckets;
        limit = (int) (loadFactor * buckets.length);
    }

    public Object delete(int code, Object key) {
        int pos = code & (buckets.length - 1);
        Node curr = buckets[pos];
        Node prev = null;
        while (curr != null) {
            if (curr.key.equals(key)) {
                if (prev == null) {
                    buckets[pos] = curr.next;
                } else {
                    prev.next = curr.next;
                }
                count--;
                return curr.val;
            }
            prev = curr;
            curr = curr.next;
        }
        return null;
    }
}

ハッシュコードの生成

ハッシュアルゴリズムとは、任意のオブジェクトに対して限られた範囲（例えばint型の範囲）の一意の数値を割り当てるプロセスである。

Object.hashCode

• ObjectクラスのhashCodeメソッドはデフォルトで乱数を生成しオブジェクトのヘッダにキャッシュする。
• 同じ値を持つ異なるオブジェクト間で異なるハッシュ値が生成されるため、オブジェクトの「値」の特徴を反映できず、多くのサブクラスでオーバーライドされる。

String.hashCode

public static void main(String[] args) {
    String s1 = "bac";
    String s2 = new String("abc");

    System.out.println(s1.hashCode());
    System.out.println(s2.hashCode());

    // 同一文字列は同一のハッシュ値を、異なる文字列は可能な限り異なるハッシュ値を生成する原則
    int hashVal = 0;
    for (int i = 0; i < s1.length(); i++) {
        char ch = s1.charAt(i);
        // 31倍は (hashVal * 32) - hashVal と等価であり、左シフトと減算で高速化可能
        hashVal = (hashVal << 5) - hashVal + ch;
    }
    System.out.println(hashVal);
}

• 大きな素数を掛けることでハッシュ衝突を減らせる経験則から、掛ける数として31が採用されている。
• 31倍は「32倍 - 元の値」と等価であり、さらに「5ビット左シフト - 元の値」という高速なビット演算に変換できる。

ハッシュテーブルの分散性検証

public void analyzeDistribution() {
    int[] counts = new int[buckets.length];
    for (int i = 0; i < buckets.length; i++) {
        Node curr = buckets[i];
        while (curr != null) {
            counts[i]++;
            curr = curr.next;
        }
    }
    System.out.println(Arrays.toString(counts));

    Map stats = Arrays.stream(counts).boxed()
        .collect(Collectors.groupingBy(c -> c, Collectors.counting()));
    System.out.println(stats);
}

考察ポイント

1. 今回の実装では連結リストの末尾に追加しているが、先頭に追加するとどうなるか？
2. JDKのHashMapでは、オブジェクトのhashCodeの上位ビットと下位ビットをXORして衝突を減らしているが、その理由は？
3. 今回のテーブル容量は2の累乗に基づき最適化しているが、2の累乗以外を容量にした場合の影響は？
4. JDKのHashMapでは連結リストが長くなりすぎると赤黒木に変換されるが、これに対する見解は？

アルゴリズム問題への応用

E01. 2つの合計 (LeetCode 1)

public int[] findTwoSum(int[] numbers, int target) {
    Map indexMap = new HashMap<>();
    for (int i = 0; i < numbers.length; i++) {
        int complement = target - numbers[i];
        if (indexMap.containsKey(complement)) {
            return new int[]{i, indexMap.get(complement)};
        }
        indexMap.put(numbers[i], i);
    }
    return null;
}

E02. 最長の部分文字列の重複なし文字数 (LeetCode 3)

public int maxUniqueLength(String str) {
    Map charPos = new HashMap<>();
    int left = 0;
    int maxLen = 0;
    for (int right = 0; right < str.length(); right++) {
        char c = str.charAt(right);
        if (charPos.containsKey(c)) {
            // 重複発見時、左ポインタを過去の重複位置か現在の左位置の大きい方に移動
            left = Math.max(left, charPos.get(c) + 1);
        }
        charPos.put(c, right);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

文字種が限定されている場合は配列で代用可能。

public int maxUniqueLength(String str) {
    int[] positions = new int[128];
    Arrays.fill(positions, -1);
    int left = 0;
    int maxLen = 0;
    for (int right = 0; right < str.length(); right++) {
        char c = str.charAt(right);
        if (positions[c] != -1) {
            left = Math.max(left, positions[c] + 1);
        }
        positions[c] = right;
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

E03. アナグラムのグループ化 (LeetCode 49)

解法1: ソート済みの文字列をキーとする

public List collectAnagrams(String[] words) {
    Map groups = new HashMap<>();
    for (String word : words) {
        char[] chars = word.toCharArray();
        Arrays.sort(chars);
        String sorted = new String(chars);
        groups.computeIfAbsent(sorted, k -> new ArrayList<>()).add(word);
    }
    return new ArrayList<>(groups.values());
}

解法2: 文字の頻度をカスタムキーとする

static class CharCounter {
    int[] freq = new int[26];

    CharCounter(String word) {
        for (char ch : word.toCharArray()) {
            freq[ch - 'a']++;
        }
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        return Arrays.equals(freq, ((CharCounter) o).freq);
    }

    @Override
    public int hashCode() {
        return Arrays.hashCode(freq);
    }
}

public List collectAnagrams(String[] words) {
    Map groups = new HashMap<>();
    for (String word : words) {
        groups.computeIfAbsent(new CharCounter(word), k -> new ArrayList<>()).add(word);
    }
    return new ArrayList<>(groups.values());
}

E04. 重複要素の検出 (LeetCode 217)

public boolean hasDuplicate(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int num : nums) {
        if (!seen.add(num)) return true;
    }
    return false;
}

E05. 1回だけ出現する要素 (LeetCode 136)

解法1: HashSetを利用

public int findUnique(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        if (!set.add(num)) set.remove(num);
    }
    return set.iterator().next();
}

解法2: XOR演算を利用

public int findUnique(int[] nums) {
    int res = 0;
    for (int num : nums) {
        res ^= num;
    }
    return res;
}

E06. アナグラムの判定 (LeetCode 242)

public boolean isAnagram(String s, String t) {
    return Arrays.equals(buildFreq(s), buildFreq(t));
}

private int[] buildFreq(String str) {
    int[] freq = new int[26];
    for (char ch : str.toCharArray()) {
        freq[ch - 'a']++;
    }
    return freq;
}

E07. 最初の非重複文字 (LeetCode 387)

public int firstUniqueIndex(String str) {
    int[] freq = new int[26];
    for (char ch : str.toCharArray()) {
        freq[ch - 'a']++;
    }
    for (int i = 0; i < str.length(); i++) {
        if (freq[str.charAt(i) - 'a'] == 1) return i;
    }
    return -1;
}

E08. 最頻出単語 (LeetCode 819)

正規表現を使わず文字単位で処理することで高速化可能。

public String frequentWord(String text, String[] banned) {
    Set<String> banSet = Set.of(banned);
    Map counts = new HashMap<>();
    char[] chars = text.toLowerCase().toCharArray();
    StringBuilder sb = new StringBuilder();

    for (char ch : chars) {
        if (ch >= 'a' && ch <= 'z') {
            sb.append(ch);
        } else {
            processWord(sb, banSet, counts);
            sb.setLength(0); // 毎回新しいインスタンスを生成しない最適化
        }
    }
    processWord(sb, banSet, counts);

    String result = null;
    int maxCount = 0;
    for (Map.Entry entry : counts.entrySet()) {
        if (entry.getValue() > maxCount) {
            maxCount = entry.getValue();
            result = entry.getKey();
        }
    }
    return result;
}

private void processWord(StringBuilder sb, Set<String> banSet, Map counts) {
    if (sb.length() > 0) {
        String word = sb.toString();
        if (!banSet.contains(word)) {
            counts.merge(word, 1, Integer::sum);
        }
    }
}

E09. 前順序と中順序から二分木を構築 (LeetCode 105 改善版)

class TreeBuilderPreIn {
    Map inorderMap = new HashMap<>();

    public TreeNode construct(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        return build(preorder, 0, 0, inorder.length - 1);
    }

    private TreeNode build(int[] pre, int preIdx, int inStart, int inEnd) {
        if (inStart > inEnd) return null;
        int val = pre[preIdx];
        TreeNode node = new TreeNode(val);
        int rootIdx = inorderMap.get(val);
        int leftCount = rootIdx - inStart;
        node.left = build(pre, preIdx + 1, inStart, rootIdx - 1);
        node.right = build(pre, preIdx + 1 + leftCount, rootIdx + 1, inEnd);
        return node;
    }
}

E10. 中順序と後順序から二分木を構築 (LeetCode 106 改善版)

class TreeBuilderInPost {
    Map inorderMap = new HashMap<>();

    public TreeNode construct(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        return build(postorder, postorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode build(int[] post, int postIdx, int inStart, int inEnd) {
        if (inStart > inEnd) return null;
        int val = post[postIdx];
        TreeNode node = new TreeNode(val);
        int rootIdx = inorderMap.get(val);
        int rightCount = inEnd - rootIdx;
        node.left = build(post, postIdx - 1 - rightCount, inStart, rootIdx - 1);
        node.right = build(post, postIdx - 1, rootIdx + 1, inEnd);
        return node;
    }
}