概念
顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键 码的多次比较。顺序查找时间复杂度为O(N),平衡树中为树的高度,即O( log2N),搜索的效率取决于搜索过程中 元素的比较次数。 理想的搜索方法:可以不经过任何比较,一次直接从表中得到要搜索的元素。 如果构造一种存储结构,通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系,那么在查找时通过该函数可以很快找到该元素。 当向该结构之中插入元素时,根据该元素的关键码和特定的函数计算出该元素应存放的位置,并且按此位置存放,而在取元素时按同样方式计算出所处位置。这样的话,存储和查找的时间复杂度就可以达到O(1)。 该方式即为哈希(散列)方法,用到的函数称为哈希(散列)函数。构造出来的结构称为哈希表或散列表哈希函数设置为: hash(key) = key % capacity ; capacity 为存储元素底层空间总的大小。 比如一个长度为10的数组 如果要放13,hash(13)=13%10=3所以放在3下标,但如果要放14,会出现什么问题?
冲突(碰撞)
1.概念:
对于两个数据元素的关键字 和 (i != j) ,有ki != kj ,但有: Hash(ki ) == Hash( kj) ,即: 不同关键字通过相同哈 希函数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞 。
2.冲突的发生是必然的,我们要做的就是降低冲突率
3.冲突的避免–哈希函数的设计
引起哈希冲突的一个原因可能是: 哈希函数设计不够合理 。 希函数设计原则 : 哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许有 m 个地址时,其值域必须在 0 到 m-1 之间 哈希函数计算出来的地址能均匀分布在整个空间中 哈希函数应该比较简单
1.直接定制法(常用)
取关键字的某个线性函数为散列地址: Hash ( Key ) = A*Key + B。优点:简单均匀;缺点:需要事先知道关键字的分布情况;使用场景:适合于查找比较小且连续的情况。 例如:Hash(key)=key-minval;对于数据97,95,91,93,96,minval是91,所以将97放到6下标,95放到4下标…… 2.除留余数法 散列表中允许的地址数是m(就是下标从0到m,注意哈希表的底层首先是一个数组),那么就取小于等于m,接近于m的质数p作为除数,用函数 hash(key) = key %p来求得地址 3. 平方取中法–(了解) 假设关键字为1234,对它平方就是1522756,抽取中间的3位227作为哈希地址; 再比如关键字为4321,对 、它平方就是18671041,抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合:不知道关键字的分布,而位数又不是很大的情况 4. 折叠法–(了解)折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些),然后将这几部分叠加求和, 并按散列表表长,取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布,适合关键字位数比较多的情况 5. 随机数法–(了解) 选择一个随机函数,取关键字的随机函数值为它的哈希地址,即H(key) = random(key),其中random为随机数函数。通常应用于关键字长度不等时采用此法 6. 数学分析法–(了解) 设有n个d位数,每一位可能有r种不同的符号,这r种不同的符号在各位上出现的频率不一定相同,可能在某些位上分布比较均匀,每种符号出现的机会均等,在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小,选择其中各种符号分布均匀的若干位作为散列地址。 注意:哈希函数设计的越精妙,产生哈希冲突的可能性就越低,但是无法避免哈希冲突
4.冲突的避免–负载因子调节
散列表的载荷因子(负载因子)=填入表中的元素/散列表的长度
由于表长是定值,所以填入的元素越多,负载因子越大,产生冲突的可能性就越大。一般要将载荷因子控制在0.75以下,当超过0.75时,就应该对哈希表中的数组进行扩容
5.冲突的解决之闭散列
闭散列:也叫开放地址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以 把key存放到冲突位置中的“下一个” 空位置中去。那么如何找到下一个空位置呢? 法一:线性探测从发生冲突的位置开始,依次向后进行探测,直到找到下一个空位置。缺陷是产生冲突的元素会堆积在一块,例如:想要插入11,21,31,41,就会依次放到2,3,8,0下标 法二:二次探测 找下一个空位置的方法为:Hi = (H0+ i^2)% m, 或者: Hi= (H0-i^2 )% m。其中:H0是通过哈希函数计算出的下标, i = 1,2,3… ,表示的是发生冲突的次数,例如想要放21,通过哈希函数计算出来是1,即H0=1,这是第一次发生冲突,所以i=1,所以Hi= (H0+i^2 )% m即Hi=(1+1)%10=2。
6.冲突的解决之开散列(哈希桶)
开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子 集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。 比如要放11,通过散列函数计算出下标为1,所以可以通过头插法或者尾插法将11查到对应的链表里 这就是我们所说的哈希表实际上是数组+链表+红黑树(当数组长度>=64&&链表长度>=8以后,就会将其变成一棵红黑树) java的HashMap就是用这种哈希表的方式来解决哈希冲突的
7.哈希桶的实现
首先注意,哈希桶是一个数组,数组的元素其实就是每个链表的头节点
放置元素:
首先要找到对应链表,然后遍历该链表,如果某个结点的key等于待插入结点的key,就更新该节点的value值,然后结束该方法即可;如果没有对应的key,就通过头插法或者尾插法插入该节点,代码如下:
但这样是有缺陷的,我们之前提到了负载因子最好不超过0.75,所以我们再加一个方法返回当前的负载因子,如果大于0.75就进行扩容,代码如下:
首先添加一个成员变量,即默认最大负载因子
然后是计算负载因子
最后是在put方法的最后进行扩容。
但这样的扩容不对!!!因为数组长度变了,对应的key所在的下标就会变!!!,所以代码应为(我用的头插法扩容):
获得value:
HashMap,HasSet的实现
1.Map不支持迭代器遍历,因为它没有实现Iterable接口,要想用迭代器,就必须将Map转化成Set
2.Map中的对象不需要必须可比较,因为他是通过Hash函数来计算所处位置,而不是通过大小比较。并且key或value可以是null,如下:
3.HashMap和HashSet一样是可以天然去重的,(TreeSet,TreeMap也一样)如下:
4.HashMap,HashSet对象不一定可比较,key也不一定是一个整数,那么系统是怎么找到对应的下标从而将键值对放进去的呢?这就用到了HashCode方法来生成一个整数。看源码:
当key不是null时,就会调用key的hashCode方法,如果key本身没有hashCode方法,就会调用Object类的方法:
这段话的意思是,在合理情况下,不同的对象会返回不同的整数,这通常是将对象的内部地址转换为整数实现的,所以下面的情况,即使Student的id是相同的,产生的hashCode也是不同的,如下
要想产生同样的整数,就可以重写hashCode方法:
这是我们根据上面的源码自己重写的方法,调用了hash方法,传参时直接传入id,但最好是通过编译器直接生成hashCode方法,同时一并重写equals方法
如果不重写equals方法,相同id的对象jinxingequals方法后产生的结果是false,因为源码中equals是根据对象的地址比较的
哈希桶的优化代码
我们将哈希桶写成一个泛型类,并让其可以通过各种类型的key生成对应的整数,代码如下:
1.放置键值对:
2.根据key得到对应的value
看下面的一段代码:
student1和student2的id是一样的,而且我们重写了hashCode方法,所以说,虽然我们只在哈希桶里面放置了student1,但在根据student2取元素时,得到的也应该是10,但结果却如下:
这是因为put函数和getval函数有一句是错的,即if(cur.key==key),应该用equals方法,代码如下: