黑马程序员技术交流社区

标题: 关于一道百度的面试题关于HashMap的内部实现机制 [打印本页]
作者: 贺洪京    时间: 2011-10-29 19:03
标题: 关于一道百度的面试题关于HashMap的内部实现机制
关于一道百度的面试题关于HashMap的内部实现机制，望各位大侠们指点指点，小弟不胜感激
作者: 张强+    时间: 2011-10-30 16:55


1.    HashMap概述：
   HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。


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

file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\ksohtml\wps_clip_image-15788.png
从上图中可以看出，HashMap底层就是一个数组结构，数组中的每一项又是一个链表。当新建一个HashMap的时候，就会初始化一个数组。

源码如下：
view source
file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\ksohtml\wps_clip_image-11086.png
print?
01

/**
02
* The table, resized as necessary. Length MUST Always be a power of two.

03
*/
04
transient Entry[] table;

05

06
static class Entry<K,V> implements Map.Entry<K,V> {

07
    final K key;
08
    V value;

09
    Entry<K,V> next;
10
    final int hash;

11
    ……
12
}
可以看出，Entry就是数组中的元素，每个 Map.Entry 其实就是一个key-value对，它持有一个指向下一个元素的引用，这就构成了链表。


[size=10.5000pt]
[size=10.5000pt]





欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2