2014阿里实习面试题——哈希的原理和Java中HashMap如何实现的

1、哈希的原理哈希的出现时因为传统数据结构如线性表（数组，链表等），树中，关键字与其它的存放位置不存在对应的关系。因此在查找关键字的时候需要逐个比对，虽然出现了二分查找等各种提高效率的的查找算法。但是这些并不足够，希望在查询关键字的时候不经过任何比较，一次存取便能得到所查记录。因此，我们必须在关键字和其对应的存储位置间建立对应的关系f。这种对应的关系f被称为哈希函数，按此思想建立的表为哈希表。关键在于哈希函数如何构造。有如下几种方法：1）直接定址法取关键字或者关键字的某个线性函数值为哈希地址。2）数字分析法3）平方取中法取关键字平方后的中间几位为哈希地址。4）折叠法将关键字分割成位数相同的几部分（最后一部分的位数可以不通），然后取这几部分的叠加和（舍去进位）作为哈希地址。5）取余数法取关键字被某个不大于哈希表表长（HASH_TABLE_LENGTH）的数p除后所得的余数作为哈希地址。H（key） = key % p （其中p小于或者等于哈希表表长HASH_TABLE_LENGTH）6）随机数法取关键字的随机函数值作为它的哈希地址。那么确定了哈希函数之后，就要解决哈希冲突的问题，常用的方法如下：1）开放定址法Hi = （H（key） + di） % M i = 1, 2, 3,..., k （ k <= M-1 ）其中：H（key）为哈希函数；M为哈希表表长；di为增量序列；di可能有下列三种取法：a 线性探测再散列：di = 1, 2, 3, ..., M-1b 二次探测再散列：di = （+,-）k^2，（k <= M/2）c 随机探测再散列：di为随机数序列2）再哈希法3）链地址法4）建立一个公共溢出区2、java中的hashmap是如何实现的HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。我们可以理解为“链表的数组”，如图：HashMap其实也是一个线性的数组实现的,所以可以理解为其存储数据的容器就是一个线性数组。那么一个线性的数组怎么实现按键值对来存取数据呢？这里HashMap有做一些处理。 1.首先HashMap里面实现一个静态内部类Entry，其重要的属性有 key , value, next，从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean，我们上面说到HashMap的基础就是一个线性数组，这个数组就是Entry[]，Map里面的内容都保存在Entry[]里面。2、hashmap中hash冲突的解决（链地址法）：Entry类里面有一个next属性，作用是指向下一个Entry。每当同一个index有新的结点（A）插入时，A成为此索引的头结点，然后A->NEXT=旧头结点。本文永久更新链接地址：http://www.linuxidc.com/Linux/2014-04/100598.htm