HashMap的工作原理及实现

HashMap的工作原理

        HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，然后找到bucket位置来储存值对象。当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。HashMap使用LinkedList来解决碰撞问题，当发生碰撞了，对象将会储存在LinkedList的下一个节点中。HashMap在每个LinkedList节点中储存键值对对象。

       当两个不同的键对象的hashcode相同时会发生什么？它化会储存在同一个bucket位置的LinkedList中。键对象的equals()方法用来找到键值对。

 

Java实现：

    1.Node节点类：

class Node<K, V> {
    private final K key;
    private V value;
    private Node<K, V> next;

    public Node(K key, V value) {
        this.key = key;
        this.value = value;
    }

    public V getValue() {
        return value;
    }

    public void setValue(V value) {
        this.value = value;
    }

    public Node<K, V> getNext() {
        return next;
    }

    public void setNext(Node<K, V> next) {
        this.next = next;
    }

    public K getKey() {
        return key;
    }
}

   2.HashMap<K,V>实现类

public class HashMap<K, V> {
    private static int DEFAULT_CAPACITY = 16;
    private static double A = (Math.pow(5, 0.5) - 1) / 2;

    private int capacity;
    private int size = 0;

    private Node<K, V>[] buckets;

    public HashMap() {
        this(DEFAULT_CAPACITY);
    }

    @SuppressWarnings("unchecked")
    public HashMap(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException(
                    "capacity can not be negative or zero");
        }

        // 保证 capacity 是2的n次方
int temp = 1;
        while (temp < capacity) {
            temp <<= 2;
        }
        this.capacity = temp;

        buckets = new Node[this.capacity];
    }

    public void insert(K key, V value) {
        if (key == null) {
            throw new IllegalArgumentException("key can not be null");
        }

        int position = index(key);

        Node<K, V> node = new Node<K, V>(key, value);
        if (buckets[position] != null) {
            node.setNext(buckets[position]);
        }

        buckets[position] = node;
        size++;
    }

    public void put(K key, V value) {
        if (key == null) {
            throw new IllegalArgumentException("key can not be null");
        }

        int position = index(key);

        Node<K, V> node = buckets[position];

        while (node != null) {
            if (node.key.equals(key)) {
                node.value = value;
                return;
            }

            node = node.next;
        }

        Node<K, V> newNode = new Node<K, V>(key, value);
        if (buckets[position] != null) {
            newNode.setNext(buckets[position]);
        }

        buckets[position] = newNode;
        size++;
    }

    public void delete(K key) {
        if (key == null) {
            throw new IllegalArgumentException("key can not be null");
        }

        int position = index(key);
        Node<K, V> node = buckets[position];

        if (node == null) {
            return;
        }

        if (node.key.equals(key)) {
            buckets[position] = node.next;
            size--;
        }

        while (node.next != null) {
            if (node.next.key.equals(key)) {
                node.next = node.next.next;
                size--;
                break;
            }

            node = node.next;
        }
    }

    public V search(K key) {
        if (key == null) {
            throw new IllegalArgumentException("key can not be null");
        }

        int position = index(key);
        Node<K, V> node = buckets[position];

        while (node != null) {
            if (node.key.equals(key)) {
                return node.value;
            }

            node = node.next;
        }

        return null;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    @Override
public String toString() {
        StringBuffer buffer = new StringBuffer();
        buffer.append("{");

        for (int i = 0; i < capacity; i++) {
            Node<K, V> node = buckets[i];
            while (node != null) {
                buffer.append(node.key + ":" + node.value + ", ");
                node = node.next;
            }
        }

        if (buffer.length() > 1) {
            buffer.delete(buffer.length() - 2, buffer.length());
        }

        buffer.append("}");

        return buffer.toString();
    }

    private int index(K key) {
        int hashCode = key.hashCode();

        double temp = hashCode * A;
        double digit = temp - Math.floor(temp);

        return (int) Math.floor(digit * capacity);
    }

   public static void main(String[] args) {
        HashMap<String, String> map = new HashMap<String, String>();
        map.put("001","apple");
        map.put("002","orange");
        map.put("003","banana");
        map.put("004","grape");
                System.out.println(map);
        System.out.println(map.size());
        System.out.println(map.search("004"));
   }
}