阿里实习面试题——哈希的原理和Java中HashMap如何达成的
发布时间:2021-11-20 16:21:45 所属栏目:教程 来源:互联网
导读:1、哈希的原理 哈希的出现时因为传统数据结构如线性表(数组,链表等),树中,关键字与其它的存放位置不存在对应的关系。因此在查找关键字的时候需要逐个比对,虽然出现了二分查找等各种提高效率的的查找算法。但是这些并不足够,希望在查询关键字的时候不经
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-1 b 二次探测再散列: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=旧头结点。 (编辑:东莞站长网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |