Java中HashMap的实现原理

一、HashMap概述

        HashMap是基于Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键，但此类不保证映射的顺序（不保证元素顺序恒久不变）。

        在java编程语言中，最基本的结构就是两种：数组和模拟指针（引用），其他所有的数据结构都可以基于它们构造出来，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。

        从上图中可以看出，HashMap底层是一个数组结构，数组中的每一项又是一个链表，链表中的结点是Entry类型的对象实例。当新建一个HashMap的时候，就会初始化一个数组。其Java源码如下：

// The table, resized as necessary. Length MUST Always be a power of two. transient Entry[] table; static class Entry<K, V> implements Map.Entry<K, V> { final K key; V value; Entry<K, V> next; final int hash; }