java面试题网

普通会员

108

帖子

11

回复

136

积分

楼主
发表于 2018-05-25 14:12:17 | 查看: 579| 回复: 0
  • HashMap 的基本组成成员

   首先,HashMap 是 Map 的一个实现类,它代表的是一种键值对的数据存储形式。Key 不允许重复出现,Value 随意。jdk 8 之前,其内部是由数组+链表来实现的,而 jdk 8 对于链表长度超过 8 的链表将转储为红黑树。HashMap底层就是一个数组结构,数组中的每一项又是一个链表。当新建一个HashMap的时候,就会初始化一个数组。

   源码如下:

/** 

 * 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;  

    ……  

}  

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


  • put 方法的具体实现

public V put(K key, V value) {  

    // HashMap允许存放null键和null值。  

    // 当key为null时,调用putForNullKey方法,将value放置在数组第一个位置。  

    if (key == null)  

        return putForNullKey(value);  

    // 根据key的keyCode重新计算hash值。  

    int hash = hash(key.hashCode());  

    // 搜索指定hash值在对应table中的索引。  

    int i = indexFor(hash, table.length);  

    // 如果 i 索引处的 Entry 不为 null,通过循环不断遍历 e 元素的下一个元素。  

    for (Entry<K,V> e = table[i]; e != null; e = e.next) {  

        Object k;  

        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  

            V oldValue = e.value;  

            e.value = value;  

            e.recordAccess(this);  

            return oldValue;  

        }  

    }  

    // 如果i索引处的Entry为null,表明此处还没有Entry。  

    modCount++;  

    // 将key、value添加到i索引处。  

    addEntry(hash, key, value, i);  

    return null;  

}  

     当我们往HashMap中put元素的时候,先根据key的hashCode重新计算hash值,根据hash值得到这个元素在数组中的位置(即下标),如果数组该位置上已经存放有其他元素了,那么在这个位置上的元素将以链表的形式存放,新加入的放在链头,最先加入的放在链尾。如果数组该位置上没有元素,就直接将该元素放到此数组中的该位置上。

    

  • remove 方法的具体实现。

     采用迭代器遍历,不仅适用于HashMap,对其它类型的容器同样适用。

   采用这种方法的遍历,可以用下文提及的方式安全地对HashMap内的元素进行修改,并不会对后续的删除操作造成影响。

  如果使用foreach遍历方法删除HashMap中的元素,Java很有可能会在运行时抛出异常。

    为什么呢?

    1、使用iterator迭代删除时没有问题的,在每一次迭代时都会调用hasNext()方法判断是否有下一个,是允许集合中数据增加和减少的。

    2、使用forEach删除时,会报错ConcurrentModificationException,因为在forEach遍历时,是不允许map元素进行删除和增加。

    所以,遍历删除map集合中元素时,必须使用迭代iterator

  • 为什么时HashMap的容量总是2的n次方?

    如果不是2的2次幂,空间浪费相当大,更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率,减慢了查询的效率!而当数组长度为16时,即为2的n次方时,2n-1得到的二进制数的每个位上的值都为1,这使得在低位上&时,得到的和原hash的低位相同,加之hash(int h)方法对key的hashCode的进一步优化,加入了高位计算,就使得只有相同的hash值的两个值才会被放到数组中的同一个位置上形成链表。

    

  • 其他一些基本方法的基本介绍

   HashMap 包含如下几个构造器:

   HashMap():构建一个初始容量为 16,负载因子为 0.75 的 HashMap。

   HashMap(int initialCapacity):构建一个初始容量为 initialCapacity,负载因子为 0.75 的 HashMap。

   HashMap(int initialCapacity, float loadFactor):以指定初始容量、指定的负载因子创建一个 HashMap。

   HashMap的基础构造器HashMap(int initialCapacity, float loadFactor)带有两个参数,它们是初始容量initialCapacity和加载因子loadFactor。

   initialCapacity:HashMap的最大容量,即为底层数组的长度。

   loadFactor:负载因子loadFactor定义为:散列表的实际元素数目(n)/ 散列表的容量(m)。

  • 什么是红黑树

红黑树本质上是一种二叉查找树,但它在二叉查找树的基础上额外添加了一个标记(颜色),同时具有一定的规则。这些规则使红黑树保证了一种平衡,插入、删除、查找的最坏时间复杂度都为 O(logn)。



您需要登录后才可以回帖 登录 | 立即注册

java面试题网无聊看看网与java建站系统提供技术支持V2.1 网站地图 © 2016-2018