你的位置:首页 > Java教程

[Java教程]一步一步学J2SE

HashMap数据结构图

  HashMap的数据结构是通过数组加链表实现的。数组是HashMap的主体,链表是为了解决Hash碰撞问题。

  

HashMapPut方法

1、  在put的时候首先判断key值是不是null,如果是null,则处理null值为key所放的位置

2、  如果key值不为null,则对key值进行hash运算,如果得到的值在数组的位置没有其他的Entry,则将该值放到数组的相应的位置

3、  如果hash之后,在数组的位置已经有值了,说明发生了碰撞,会跟该位置的所有Entry的key值进行比较

4、  如果比较的key值相同,则说明是同一个元素,则会用新的value值替换旧的value值,然后返回旧的value值

5、  如果key值不相同,则说明不是同一个元素,则将该元素放在链表的第一个位置。

HashMap的Get方法

1、  在get的时候首先判断key值是不是null,如果是null,则取key为null的值所在位置的值。

2、  如果key不为null,首先计算出key的hashCode,然后在数组中的对应位置取值。

3、  跟数组相应位置的key进行hashCode和equals比较,如果相等,则取出该Entry的值。

HashMap的resize

         当HashMap中的元素越来越多的时候,hash冲突的几率也就越来越高,因为数组的长度是固定的。所以为了提高查询效率,就要对HashMap的数组进行扩容,HashMap的扩容会对原数组中的数据重新计算其在数组中的位置,并放进去。所以这个操作很耗性能。

         那么HashMap什么时候扩容呢?当HashMap中元素的个数超过数组大小*loadFactor时,就会进行数组扩容。loadFactor的默认值是0.75。当达到这个条件的时候,就会对数组的大小进行扩容,扩大一倍。然后重新计算每个元素在数组中的位置。所以如果我们能够预知HashMap中元素的个数,那么预设元素的个数能够有效的提高HashMap的性能。

HashMap的Fail-Fast机制

         HashMap是线程不安全的,所以如果在迭代器迭代的过程中有其他线程修改了map,那么将抛出ConcurrentModificationException,这就是fail-fast机制。

         在HashMap中有一个modCount域,记录了HashMap的修改次数,每次对HashMap的内容修改都会增加这个值。在迭代器初始化的过程中,迭代器会记录这个值。

         在迭代器的迭代过程中,每次取数据之前,都会对比modCount的值和自己保存的值是否相等,如果不相等,说明HashMap被修改了,则抛出异常。