MyException - 我的异常网
当前位置:我的异常网» 互联网 » java中hashMap相干的面试题

java中hashMap相干的面试题

www.MyException.Cn  网友分享于:2014-08-05  浏览:0次
java中hashMap有关的面试题

最近整理一下面试中hashMap会问到的几个知识点:

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

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

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

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

HashMap中有一个内部类Entry,

 

?
1
2
3
4
5
6
7
static class Entry<k,v> implements Map.Entry<k,v> {
        final K key;
        V value;
        Entry<k,v> next;
        int hash;
        //.....
}</k,v></k,v></k,v>
主要有4个属性,key ,hash,value,指向下一个节点的引用next ,看到这个实体类就明白了,在HashMap中存放的key-value实质是通过实体类Entry来保存的

 

面试题: hashMap的实现原理?

1:hashMap是基于哈希表的Map接口的一个非同步实现,并允许空值空键,此类并不保证映射的顺序,特别是它不保证顺序恒久不变。

2:hashMap的数据结构,其实是一个“链表散列”式的数据结构,即数组和链表的结合体。

3:hashMap的功能是通过key能够迅速的找到值。

按照散列函数的定义,如果两个对象相同,即obj1.equals(obj2)=true,则它们的hashCode必须相同,但如果两个对象不同,则它们的hashCode不一定不同。

如果两个不同对象的hashCode相同,这种现象称为冲突,冲突会导致操作哈希表的时间开销增大,所以尽量定义好的hashCode()方法,能加快哈希表的操作。

如果相同的对象有不同的hashCode,对哈希表的操作会出现意想不到的结果(期待的get方法返回null),

再回头看看前面提到的为什么覆盖了equals方法之后一定要覆盖hashCode方法,很简单,比如,String a = new String(“abc”);String b = new String(“abc”);如果不覆盖hashCode的话,那么abhashCode就会不同,把这两个类当做key存到HashMap中的话就 会出现问题,就会和key的唯一性相矛盾

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这个属性链接在一起。也就是说数组中存储的是最后插入的元素。

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
}</k,v>
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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) {//这个方法就验证了上面说的<strong>数组中存储的是最后插入的元素</strong>
    Entry<k,v> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}</k,v>
面试题: hashMap的get过程?
这个过程比较简单,直接看代码:
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
}</k,v>
面试题: hashMap存取的时候是如何定位数组下标的?
找到indexFor这个方法,hashMap就是通过这个方法获取数组下标的:

 

 

?
1
2
3
static int indexFor(int h, int length) {
        return h & (length-1);
    }
通过key的hash值和数组长度求&,这意味着数组下标相同,并不表示hashCode相同。所以在Entry中存有一个hash值,在比较Entry的时候都是想比较hash值
面试题: hashMap中数组的初始化大小过程?

 

找到hashMap的构造方法:

 

?
1
2
3
4
5
6
7
8
9
10
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,重新创建一个新的表,将原表的映射到新表中,这个过程很费时。

1.    HashMap概述

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

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

3.   HashMap的存取

    HashMap的功能是通过“键(key)”能够快速的找到“值”。下面我们分析下HashMap存数据的基本流程: 

3.HashMapHashtable的区别:

HashMap可以接受null键值和值,而Hashtable则不能

Hashtable是线程安全的,通过synchronized实现线程同步。而HashMap是非线程安全的,但是速度比Hashtable快。

4.如果两个键的hashcode相同,你如何获取值对象 

HashMap在链表中存储的是键值对,找到哈希地址位置之后,会调用keys.equals()方法去找到链表中正确的节点,最终找到要找的值对象

5.如果HashMap的大小超过了负载因子(load factor)定义的容量,怎么办 

HashMap默认的负载因子大小为0.75,也就是说,当一个map填满了75%空间的时候,和其它集合类(ArrayList)一样,将会创建原来HashMap大小的两倍的数组,来重新调整map的大小,并将原来的对象放入新的数组中。

6.为什么String, Interger这样的wrapper类适合作为键?

String, Interger这样的wrapper是final类型的,具有不可变性,而且已经重写了equals()hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的,因为为了要计算hashCode(),就要防止键值改变,如果键值在放入时和获取时返回不同的hashcode的话,那么就不能从HashMap中找到你想要的对象。 

7.ConcurrentHashMapHashtable的区别

HashtableConcurrentHashMap有什么分别呢?它们都可以用于多线程的环境,但是当Hashtable的大小增加到一定的时候,性能会急剧下降,因为迭代时需要被锁定很长的时间。因为ConcurrentHashMap引入了分割(segmentation),不论它变得多么大,仅仅需要锁定map的某个部分,而其它的线程不需要等到迭代完成才能访问map。简而言之,在迭代的过程中,ConcurrentHashMap仅仅锁定map的某个部分,而Hashtable则会锁定整个map

8.HashMap的遍历

第一种:
  Map map = new HashMap();
  Iterator iter = map.entrySet().iterator();
  while (iter.hasNext()) {
  Map.Entry entry = (Map.Entry) iter.next();
  Object key = entry.getKey();
  Object val = entry.getValue();
  }
  效率高,以后一定要使用此种方式!
第二种:
  Map map = new HashMap();
  Iterator iter = map.keySet().iterator();
  while (iter.hasNext()) {
  Object key = iter.next();
  Object val = map.get(key);
  }
  效率低,以后尽量少使用!

可是为什么第一种比第二种方法效率更高呢?

HashMap这两种遍历方法是分别对keysetentryset来进行遍历,但是对于keySet其实是遍历了2次,一次是转为iterator,一次就从hashmap中取出key所对于的value。而entryset只是遍历了第一次,它把keyvalue都放到了entry,即键值对,所以就快了。

先总结到这吧,以后遇到有价值的hashmap相关的题目日后再做更新,文章不足之处,反应各位拍砖指正。。。。

 

 

 

 

文章评论

代码女神横空出世
代码女神横空出世
 程序员的样子
程序员的样子
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
老程序员的下场
老程序员的下场
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
旅行,写作,编程
旅行,写作,编程
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
编程语言是女人
编程语言是女人
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
程序员和编码员之间的区别
程序员和编码员之间的区别
10个调试和排错的小建议
10个调试和排错的小建议
那些争议最大的编程观点
那些争议最大的编程观点
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
如何成为一名黑客
如何成为一名黑客
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
漫画:程序员的工作
漫画:程序员的工作
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
总结2014中国互联网十大段子
总结2014中国互联网十大段子
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
程序员应该关注的一些事儿
程序员应该关注的一些事儿
我是如何打败拖延症的
我是如何打败拖延症的
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
一个程序员的时间管理
一个程序员的时间管理
我的丈夫是个程序员
我的丈夫是个程序员
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
程序员都该阅读的书
程序员都该阅读的书
中美印日四国程序员比较
中美印日四国程序员比较
程序员必看的十大电影
程序员必看的十大电影
每天工作4小时的程序员
每天工作4小时的程序员
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有