4.2 哈希表

  在实际项目的开发，经常遇到字典的需求。所谓字典，就是把一堆key-value的键值对存入容器中，用key作为条件能快速查出value。几乎每一种编程语言都实现了字典，但是C语言标准库没有字段的实现。按照上述我对字典的定义，任何数据结构都可以实现字典。就拿数组来说，数组每个位置放上键值对，那也是个字典啊，只是性能会很差。字典的高性能实现有多种方案，常见的方案有哈希表、跳表和红黑树实现。
  哈希表的常见的实现方案是这样的：
  底层是一个数组，数组的每一项都是一个链表，哈希值相同的在一个链表上。在扩容时，需要把底层数组扩大，然后每一个元素计算在新数组的的哈希值，然后再拷贝过去。如图所示：

  扩容后就是这样的：

  哈希表并不复杂，但是一定要动手练一练，亲自写哈希表的实现。以下是我自己的实现代码：

package com.yongthing.map.hash;

import java.util.linkedList;
import java.util.ListIterator;


public class HashMap {
    static class Entry {
        K key;
        V value;
    }

    private linkedList[] elements;
    private int size;

    public HashMap() {
        elements = new linkedList[8];
    }

    
    public void put(K key, V value) {
        if (key == null) {
            throw new IllegalArgumentException("key不能为空");
        }
        final Entry entry = new Entry<>();
        entry.key = key;
        entry.value = value;
        // 扩容
        if (size > elements.length * 0.75) {
            //elements = makeCapacity(elements);
        }
        add(entry, elements);
        size++;
    }


    public V get(K key) {
        if (key == null) {
            return null;
        }
        final int index = hash(key, this.elements);
        final linkedList element = elements[index];
        if (element == null) {
            return null;
        }
        for (Object e : element) {
            final Entry entry = (Entry) e;
            if (entry.key.equals(key)) {
                return entry.value;
            }
        }
        return null;
    }

    private static  linkedList[] makeCapacity(linkedList[] elements) {
        final linkedList[] newElements = new linkedList[(elements.length + 1) << 1];
        // 将数据拷贝过来
        for (linkedList linkedList : elements) {
            if (linkedList != null && !linkedList.isEmpty()) {
                for (Object e : linkedList) {
                    add((Entry) e, newElements);
                }
            }
        }
        return newElements;
    }

    private static  void add(Entry entry, linkedList[] elements) {
        K key = entry.key;
        final int index = hash(key, elements);
        linkedList list = elements[index];
        if (list == null) {
            list = new linkedList>();
            list.add(entry);
            elements[index] = list;
        } else {
            final ListIterator> iterator = list.listIterator();
            while (iterator.hasNext()) {
                final Entry next = iterator.next();
                if (next.key.equals(key)) {
                    // 重复时替换
                    iterator.set(entry);
                    return;
                }
            }
            // 不存在重复则添加
            list.add(entry);
        }

    }

    private static  int hash(K key, linkedList[] elements) {
        return key.hashCode() % elements.length;
    }

}