哈希表的原理

2024-03-29 10:50:16

2.哈希表的原理

2.1哈希表的结构和特点

哈希表也叫散列表
特点：快
结构：有很多种，最流行、最容易理解的是：顺序表（数组）+链表
主结构：顺序表，每个顺序表的节点再单独引出一个链表

2.2哈希表是如何添加数据的（三步）

（1）计算哈希码（调用hashCode()方法计算，返回int型，整数的哈希码取自身即可）
（2）计算在哈希表中的存储位置 y=k(x)=x%11 (11是数组的长度)
（3）存入哈希表

情况1：一次添加成功

情况2：多次添加成功（出现了冲突，即数组中已有地址，则调用equals()和对应链表的元素进行比较，比较到最后，结果都是false，创建新节点，存储数据，并加入链表末尾）

情况3：不添加（出现了冲突，即数组中已有地址，则调用equals()和对应链表的元素进行比较，经过一次或多次比较后，结果是true，表明重复，不添加）

结论1：哈希表添加数据快（3步）

结论2：唯一，无序

2.3哈希表是如何查询数据的

和添加数据过程一样（三步）。

情况1：一次找到（链表的第一个节点） 23，36，48，86

情况2：多次找到（链表的非第一个节点） 67，47

情况3：找不到（链表中找不到） 100

结论1：哈希表查询数据快（3步）

2.4 hashCode()和equals()的作用

hashCode()：计算哈希码，是一个整数，根据哈希码可以计算出数据在哈希表中的存储位置
equals():往哈希表添加数据时，出现了冲突，要通过equals()进行比较，判断是否相同；查询时也要通过equals()进行比较，判断是否相同

2.5各种类型的哈希码如何获取

int 取自身。可看Integer源码

    public int hashCode() {
        return Integer.hashCode(value);
    }
 	public static int hashCode(int value) {
        return value;
    }

double 3.24 ，4.67 取整不可以。可看Double源码

    public int hashCode() {
        return Double.hashCode(value);
    }
	public static int hashCode(double value) {
        long bits = doubleToLongBits(value);//转为long型
        return (int)(bits ^ (bits >>> 32));
    }

String 将各个字符的码值相加不可以。可看String 源码

abc：31 X (31 X（31 X 0+97）+98)+99

public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

Student 先计算各个属性的哈希码，再进行某些相加相乘的运算

String name; int age;

2.6 如何减少冲突

（1）表中记录数和哈希表的长度比例--装填因子

- 如果哈希表的空间远大于实际存储的记录数，会造成空间的浪费，如果选小了，容易造成冲突。

- 在实际情况中要根据最终存储的个数和关键字的分布特点来确定哈希表的大小。

- 事先不知道存储个数时，需动态维护哈希表的容量，此时可能需要重新计算Hash地址

装填因子=表中记录数/哈希表的长度

（2）装填因子越小，表明表中还有很多空单元，发生冲突的可能性小。

装填因子越大，发生冲突的可能性越大，查找时耗费的时间越多。

相关资料证明，装填因子在0.5左右时，Hash性能能达到最优。

所以装填因子一般取0.5

（3）哈希函数的选择

直接定址法平法取中法折叠法 除留取余法（y=x/11）

（4）处理冲突的方法

链地址法 开放地址法再散列法建立一个公共溢出区

码农公寓