赞
踩
哈希表也叫散列表,哈希表是一种数据结构,它提供了快速的插入操作和查找操作,无论哈希表总中有多少条数据,插入和查找的时间复杂度都是为O(1),因为哈希表的查找速度非常快,所以在很多程序中都有使用哈希表,例如拼音检查器等。
直接原因:
如果有一种结构 不需要数据的比较就能够找到搜索的元素,那么这种结构就是我们理想的结构,它的查找的时间复杂度为O(1)如果构造一种存储结构,通过某种函 数 (hashFunc) 使元素的存储位置与它的关键码之间能够建立一一映射的关系,那么在查找时通过该函数可以很快 找到该元素 。对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置取元素比较,若关键码相等,则搜索成功。该方式即为哈希 ( 散列 ) 方法, 哈希方法中使用的转换函数称为 哈希(散列)函数 ,构造出来的结构称为哈希表 (Hash Table)( 或者称散列表 )
如果哈希函数设置为:hash(key) = key % capacity; capacity为存储元素底层空间总的大小。
解释 此数组的capacity为10 放入1的时候 1%10 = 1 所以放到数组 1 下表
其他的也类似
问题:如果我要放入 14 的时候 14 % 10 = 4 可是目前数组4下表已经有元素了 所以14就放不进去
那么如何避免哈希冲突?----->设计合理的哈希函数
闭散列先不讲
开散列法又叫链地址法 ( 开链法 ) ,首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个 单链表 链接起来,各链表的头结点存储在哈希表中。 我们可以看到 数组中每一个有效元素的下方都是一个单链表 此 时我们再尝试放入14
就解我决了14放不进去的问题
如果哈希表中插入重复的数据会怎么样?当插入重复的数据时 会进行覆盖,保证数据唯一性
代码实现
- public class hashBucket {
- static class Node {
- private int key;
- private int val;
- Node next;
-
- public Node(int key, int val) {
- this.key = key;
- this.val = val;
- }
-
- }
- public Node[] array;
- public int usedSize;
-
- public static final double LOAD_FACTOR = 0.75;
-
- hashBucket() {
- array = new Node[10];
- }
-
- public void put(int key, int val) {
- /*
- 放入元素的时时候 如果有这个数据就覆盖 没有的话进行头插
- */
- int index = key % array.length; //数组映射关系函数
- Node cur = array[index]; //cur指向当前节点,因为要在当前的桶放入元素
- while (cur != null) {
- if(cur.key == key) { //如果有当前key 说明要进行数据覆盖
- cur.val = val;
- }
- cur = cur.next;
- }
- //走到这里说明都没有找到重复的值,此时进行头插
- Node node = new Node(key,val);
- node.next = array[index]; //可以吧array[index]看作为head头结点来进行理解
- array[index] = node;
- usedSize++;
-
- //查看是否超过了负载因子 如果超过考虑扩容
- if(LOAD_FACTOR <= loadFactor()) {
- resize();
- }
- }
- public double loadFactor() {
- //查看是否超过了负载因子
- return usedSize*1.0 / array.length;
- }
如果当前数组大小不满足需求的时候,需要对数组进行扩容。
需要注意的是,如果进行扩容 那么函数的映射关系会发生改变,也就是说要再新数组中重新映射元素。
比如 数组长度为10 此时14放到了 4 下标 扩容后数组长度为20 此时14 放到了 14 下标
代码如下
- private void resize() {
- /*
- 进行开散列扩容的时候 需要注意到可能 原有的映射关系可能不对应新的数组
- 比如 数组长度为10 此时14放到了 4 下标
- 数组长度为20 此时14 放到了 14 下标
- 所以要重新进行函数映射关系
- */
- Node[] newArray = new Node[array.length * 2]; //新数组 2倍扩容
- //重新进行映射
- for (int i = 0; i < array.length; i++) {
- Node cur = array[i]; //从旧数组的0下标开始挨个映射
-
- //在新数组中进行头插
- while (cur != null) {
- Node curNext = cur.next;
- int index = cur.key % newArray.length; //1.找到旧数组下标在新数组当中的位置
-
- cur.next = newArray[index]; //2.头插+
- newArray[index] = cur;
-
- cur = curNext;
-
- }
- }
- array = newArray;
- }
可以通过哈希函数设置元素 也可以通过哈希函数获取元素
步骤 1.先找到数组下标
2.在此下标中链式查找,如果找到就返回
- public int get(int key) {
- int index = key % array.length; //比如要找18 18在8下标的位置,肯定是链式存储
- Node cur = array[index];
- while (cur != null) {
- if(cur.key == key) {
- return cur.val;
- }
- cur = cur.next;
- }
-
- return -1;
-
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。