从哈希表（HashTable）的角度深入理解《PHP 数组的哈希碰撞攻击》

• 读博文《PHP 数组的哈希碰撞攻击》，借此机会深入学习哈希表相关知识，加深理解！
• 学习自《哈希表（HashTable）的深入理解及实际演练》 原文地址

哈希表（HashTable）概念

在记录的存储位置和它的关键字之间建立一个确定的对应关系H，以函数H(key)作为关键字为key的记录在表中的位置，这个对应关系H称为哈希（Hash）函数（又称散列函数），按这个思想建立的表为哈希表（HashTable）。

哈希函数的构建

1、直接定址法：取关键字key的一个线性函数为哈希函数，即：H(key)=a×key+b，其中a、b为常数，且a≠0。

举例：学生表关键字学号与存储位置的哈希函数：H(key)=key-1000。

2、数字分析法：若关键字是ｒ进制数，且可预知全部可能出现的关键字值，则可取关键字中若干位构成哈希地址。

举例 手机号码的后四位做为哈希地址

3、平方取中法：若关键字较短，则可先对关键字值求平方，然后取运算结果的中间几位为哈希地址。

举例：
将一组关键字(0100，0110，1010，1001，0111)平方后得(0010000，0012100，1020100，1002001，0012321)若取表长为1000，则可取中间的三位数作为散列地址集： (100，121，201，020，123)。

4、折叠法：将关键字值分割成位数相同的几个部分，然后取这几部分的叠加和（舍去进位）作为哈希地址。
5、除留余数法：取关键字被某个不大于哈希表表长 m 的数 p 除后所得余数为哈希地址。（一般情况下，p 应为质数）

举例：
设有一组关键字如下：（19,14,23,01,68,20,84,27,55,11,10,79），H(key)=key%13 。

哈希函数构建的代码演练

• 构建一个学生类：学号+姓名；
• 构建一个哈希表类：构杂志社存放学生记录的顺序数组，并初始化；

  利用简单的除留余数法，将学生学号的余数做为哈希值，并根据这个哈希值，做为顺序数组的下标，存放学生记录。

• 编写主程序进行测试

/**
 * 深入理解哈希表HashTable的代码演练
 */
public class MyHashTable {
    private Student[] addr;
    private Integer addrCount;

    MyHashTable() {
        this.addrCount = 1000;
        this.addr = new Student[this.addrCount];
        for (int i = 0; i < addr.length; i++) {
            this.addr[i] = new Student(null, null);
        }
    }

    // 用除留余数法进行哈希值运算
    private int hash(Integer key) {
        return (key % this.addrCount);
    }

    // 根据键值添加学生记录
    public void add(Integer key, Student student) {
        Integer addrIndex = hash(key);
        addr[addrIndex] = student;
    }

    // 根据键值删除学生记录
    public void remove(Integer key) {
        Integer addrIndex = hash(key);
        addr[addrIndex] = new Student(null, null);
    }

    public boolean exist(Integer key) {
        Integer addrIndex = hash(key);
        return (addr[addrIndex].getId() != null);
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("MyHashTable{");
        for (int i = 0; i < addr.length; i++) {
            stringBuilder.append("hash="+i+":");
            stringBuilder.append(addr[i].toString()+",");
        }
        stringBuilder.append("}");
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        MyHashTable myHashTable = new MyHashTable();
        myHashTable.add(1001, new Student(1001, "Jack"));
        myHashTable.add(1002, new Student(1002, "Rose"));
        myHashTable.add(1003, new Student(1003, "Mike"));
        myHashTable.add(1004, new Student(1004, "Tom"));
        myHashTable.add(1005, new Student(1005, "Mary"));
        myHashTable.add(1017, new Student(1017, "Kate"));

        if (myHashTable.exist(1001)){
            myHashTable.remove(1001);
        }
        if (myHashTable.exist(1008)){
            myHashTable.remove(1008);
        }
        System.out.println(myHashTable.toString());
    }
}

/**
 * 定义学生类
 */
class Student {
    private Integer id;
    private String name;

    Student(Integer id, String name) {
        this.id = id;
        this.name = name;
    }

    public Integer getId() {
        return id;
    }

    public void setId(Integer id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return "Student{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}

哈希地址冲突的处理

1、在以上编码演练中，可能会碰到如下情况：学号为1001的学生与学号为2001的学生，通过除留余数法，得到了同样的哈希地址，则后添加的学生记录，会与同样哈希地址的记录存在冲突。

冲突的处理办法

1、开放定址法：为产生冲突的地址H(key)再求得一个地址序列，直到不冲突为止。

线性探测再散列
平方探测再散列
随机探测再散列

2、链地址法：将所有按给定的哈希函数求得的哈希地址相同的关键字存储在同一线性链表中，且使链表按关键字有序。

哈希地址解决冲突的代码演练

/**
 * 深入理解哈希表HashTable的代码演练--接链法解决冲突
 */
public class MyHashTableLinked {
    private LinkedList<Student>[] addr;
    private Integer addrCount;

    MyHashTableLinked() {
        this.addrCount = 1000;
        this.addr = (LinkedList<Student>[]) new LinkedList[addrCount];
        for (int i = 0; i < addr.length; i++) {
            this.addr[i] = new LinkedList<Student>();
        }
    }

    // 用除留余数法进行哈希值运算
    private int hash(Integer key) {
        return (key % this.addrCount);
    }

    // 根据键值添加学生记录
    public void add(Integer key, Student student) {
        Integer addrIndex = hash(key);
        addr[addrIndex].add(student);
    }

    // 根据键值删除学生记录
    public void remove(Integer key) {
        Integer addrIndex = hash(key);
        LinkedList<Student> list = addr[addrIndex];
        if (list != null) {
            Iterator iterator = list.iterator();
            while (iterator.hasNext()) {
                Student student = (Student) iterator.next();
                list.remove(student);
            }
        }
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("MyHashTable{\r\n");
        for (int i = 0; i < addr.length; i++) {

            Iterator iterator = addr[i].iterator();
            if (iterator.hasNext()) {
                stringBuilder.append("[hash=" + i + ":");
            } else {
                continue;
            }
            while (iterator.hasNext()) {
                Student student = (Student) iterator.next();
                stringBuilder.append(student.toString() + ",");
            }
            stringBuilder.append("]\r\n");

        }
        stringBuilder.append("}");
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        MyHashTableLinked myHashTableLinked = new MyHashTableLinked();
        myHashTableLinked.add(1001, new Student(1001, "Jack"));
        myHashTableLinked.add(1002, new Student(1002, "Rose"));
        myHashTableLinked.add(1003, new Student(1003, "Mike"));
        myHashTableLinked.add(1004, new Student(1004, "Tom"));
        myHashTableLinked.add(1005, new Student(1005, "Mary"));
        myHashTableLinked.add(2001, new Student(2001, "Jerry"));
        System.out.println(myHashTableLinked.toString());

        myHashTableLinked.remove(1001);
        System.out.println(myHashTableLinked.toString());
    }
}

哈希表的查找

• 决定哈希表查找效率的是哈希函数、处理冲突的方法和哈希表的装填因子。
• 哈希表的装填因子越小，发生冲突的可能就越小，而存储空间的利用率也就越低。

// 查找
    public Student find(Integer key){
        Integer addrIndex = hash(key);
        LinkedList<Student> list = addr[addrIndex];
        if (list != null) {
            Iterator iterator = list.iterator();
            while (iterator.hasNext()) {
                Student student = (Student) iterator.next();
                if (student.getId()!=null && key.equals(student.getId())){
                    return student;
                }
            }
        }
        return null;
    }

本作品采用《CC 协议》，转载必须注明作者和本文链接