java中hashMap有关的面试题_JAVA_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > JAVA > java中hashMap有关的面试题

java中hashMap有关的面试题

 2014/10/2 18:25:04  确实比较男  程序员俱乐部  我要评论(0)
  • 摘要:面试题:Java中ArrayList和LinkedList的主要区别是什么?这个问题首先要知道数组和链表的特点数组的特点:寻址容易,插入和删除困难。链表的特点是:寻址困难,插入和删除容易。ArrayList的底层实现就是通过动态数组来实现的,LinkedLIst底层实现就是通过链表来实现的,所以直接答出数组和链表的特点就ok面试题:hashMap是怎样实现key-value这样键值对的保存?HashMap中有一个内部类Entry,staticclassEntry<K,V>
  • 标签:面试 has Map Hash Java 面试题

面试题: Java中ArrayList和LinkedList的主要区别是什么?

这个问题首先要知道数组和链表的特点

?

数组的特点:寻址容易,插入和删除困难。

链表的特点是:寻址困难,插入和删除容易。

ArrayList的底层实现就是通过动态数组来实现的,LinkedLIst底层实现就是通过链表来实现的,所以直接答出数组和链表的特点就ok

面试题:hashMap是怎样实现key-value这样键值对的保存?

HashMap中有一个内部类Entry,

?

class="html"> static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;
        //.....
}

主要有4个属性,key ,hash,value,指向下一个节点的引用next ,看到这个实体类就明白了,在HashMap中存放的key-value实质是通过实体类Entry来保存的

?

面试题:hashMap的实现原理?

HashMap使用到的数据类型主要就是数组和链表,首先看原理图

在hashMap的原理图中,左边是通过数组来存放链表的第一个节点,看懂这个图这个问题就ok

面试题:hashMap的put过程?

面我们提到过Entry类里面有一个next属性,作用是指向下一个Entry。比如说: 第一个键值对A进来,通过计算其key的hash得到的index=0,记做:Entry[0] = A。一会后又进来一个键值对B,通过计算其index也等于0,现在怎么办?HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C;这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。也就是说数组中存储的是最后插入的元素。

?

     public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {//循环判断插入的key是否已经存在,若存在就更新key对应的value
            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;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);//key不存在,那么插入新的key-value
        return null;
    }
    void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

    void createEntry(int hash, K key, V value, int bucketIndex) {//这个方法就验证了上面说的数组中存储的是最后插入的元素
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

面试题:hashMap的get过程?
这个过程比较简单,直接看代码:

public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
        //先定位到数组元素,再遍历该元素处的链表
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
}

面试题:hashMap存取的时候是如何定位数组下标的?
找到indexFor这个方法,hashMap就是通过这个方法获取数组下标的:

?

?

static int indexFor(int h, int length) {
        return h & (length-1);
    }

通过key的hash值和数组长度求&,这意味着数组下标相同,并不表示hashCode相同。所以在Entry中存有一个hash值,在比较Entry的时候都是想比较hash值
面试题:hashMap中数组的初始化大小过程?

?

找到hashMap的构造方法:

?

 public HashMap(int initialCapacity, float loadFactor) {
        .....// Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;  //相当于capacity = capacity * 2
        this.loadFactor = loadFactor;
        threshold = (int)(capacity * loadFactor);
        table = new Entry[capacity];
        init();
    }

从上面的代码我们可以看出数组的初始大小并不是构造函数中的initialCapacity!!而是2的n次方
面试题:hashMap什么时候开始rehash?
在hashMap中有一个加载因子loadFactor,默认值是0.75,当数组的实际存入值的大小 > 数组的长度×loadFactor 时候就会rehash,重新创建一个新的表,将原表的映射到新表中,这个过程很费时。

?

?

发表评论
用户名: 匿名