散列（一）

作者: 大海孤了岛 | 来源:发表于2017-03-14 13:43 被阅读48次

定义：

散列是一种用于以常数平均时间执行插入，删除和查找的技术。

我们将每个关键字被映射到从0到TableSize - 1这个范围中的某个数。这个映射称为散列函数。
散列函数需要保证任何两个不同的关键字映射到不同的单元。
当两个关键字散列到同一个值时(这叫做冲突), 应该做什么以及如何确定散列表的大小。

hash_table.png

散列函数：

一般简单合理的方法是直接返回Key mod TableSize，并且保证表的大小为素数。

a. 假设关键字是字符串，一种选择办法是将字符串的ASCII码(或Unicode码)值加起来

public static int hash(String key, int tableSize){
        int hashVal = 0;
        for (int i = 0; i < key.length(); i ++){
            hashVal += key.charAt(i);
        }
        return hashVal % tableSize;
}

这种方法实现起来简单合理，但如果表很大的话，并不会很好地分配关键字。例如，TableSize = 10007，假设所有的关键字至多8个字符长，由于ASCII码字符的值最多是127，那么它们的值是在0到1016之间，显然这不是一种均匀的分配。

*b. *假设关键字至少有三个字符，可以采用如下方法：

 public static int hash(String key, int tableSize){
        return (key.charAt(0) + key.charAt(1) * 27 + key.charAt(2) * 729) % tableSize;
 }

但这样依旧不能完全均匀地分配，因为3个字母的不同组合数实际只有2851，也就是只有大约表的28%被真正散列到。

c. 根据Horner法则计算一个(37)的多项式函数：

Paste_Image.png

public static int hash(String key, int tableSize){
        int hashVal = 0;
        for (int i = 0; i < key.length(); i ++){
            hashVal = 37 * hashVal + key.charAt(i);
        }
        hashVal %= tableSize;
        //产生负数的情况
        if (hashVal < 0){
            hashVal += tableSize;
        }
        return hashVal;
    }

解决冲突的两种方法：

分离链接法：将散列到同一个值的所有元素保留到一个表中。

开放定址法：尝试另外一些单元，直到找到空的单元为止。

*a. 分离链表法： *

separate_chaining.png

定义表的基本变量：

    //定义默认表的大小
    private static final int DEFAULT_TABLE_SIZE = 101;
    //定义表的存储
    private List<AnyType>[] theLists;
    //定义表当前的大小
    private int currentSize;

定义其构造函数，进行初始化：

    public SeparateChainingHashTable(){
        this(DEFAULT_TABLE_SIZE);
    }

    //进行初始化操作
    public SeparateChainingHashTable(int size){
        //初始化表，这里调用了一个nextPrime函数，以保证其表的大小为素数
        theLists = new LinkedList[nextPrime(size)];
        //初始化表中的链表
        for (int i = 0; i < theLists.length; i ++){
            theLists[i] = new LinkedList<AnyType>();
        }
    }

    //返回下一个素数
    private static int nextPrime(int n){
        while (!isPrime(n)){
            n ++;
        }
        return n;
    }
    //判断是否为素数
    private static boolean isPrime(int n){
        for (int i = 2; i <= Math.sqrt(n); i ++){
            if (n % i == 0 && n != 2){
                return false;
            }
        }
        return true;
    }

进行插入操作：如果这个元素是新元素，则它将被插入到链表的前端，因为往往新近插入的元素最有可能不久被访问。

    public void insert(AnyType x){
        //获取x根据hash后找到所对应的位置
        List<AnyType> whichList = theLists[myHash(x)];
        //如果当前位置链表不包含元素，则进行插入操作
        if (!whichList.contains(x)){
            //进行添加
            whichList.add(x);
            //判断是否达到表的长度，若达到则进行rehash操作，以扩大表的大小
            if (++ currentSize > theLists.length){
                rehash();
            }
        }
    }

    //根据值获取到其对应的hash位置
    private int myHash(AnyType x){
        int hashVal = x.hashCode();
        hashVal %= theLists.length;
        //考虑到负数的情况
        if (hashVal < 0){
            hashVal += theLists.length;
        }
        return hashVal;
    }

    private void rehash(){
        //获取到原来的表
        List<AnyType>[] oldLists = theLists;
        //对现有的表大小进行扩大
        theLists = new List[nextPrime(2 * theLists.length)];
        //初始化新表
        for (int j = 0; j < theLists.length; j ++){
            theLists[j] = new LinkedList<AnyType>();
        }
        //初始化大小
        currentSize = 0;
        //将旧表中的数据重新插入到新表中
        for (int i = 0; i < oldLists.length; i ++){
            for (AnyType item : oldLists[i]){
                insert(item);
            }
        }
    }

删除操作：

    //删除操作
    public void remove(AnyType x){
        //获取到对应位置的链表
        List<AnyType> whichList = theLists[myHash(x)];
        //检查是否包含元素，包含则进行删除操作，并大小--
        if (whichList.contains(x)){
            whichList.remove(x);
            currentSize --;
        }
    }

检查元素：

    //检查是否包含某个元素
    public boolean contains(AnyType x){
        List<AnyType> whichList = theLists[myHash(x)];
        return whichList.contains(x);
    }

打印链表：

    //打印链表结构
    public void printHashTable(){
        for (int i = 0; i < theLists.length; i ++){
            if (theLists[i] != null && theLists[i].size() > 0){
                System.out.println("current position is : " + i );
                for (AnyType x : theLists[i]){
                    System.out.println(x);
                }
            }
        }
    }

进行检测：为了效果更明显，我们强制表的结果为10，当然在实际项目中不可如此，这里只是为了测试作用。

public static void main(String[] args){
        int[] arr = {0, 81,1, 64,4, 25,36,16,49,9};
        SeparateChainingHashTable<Integer> separateChainingHashTable = new SeparateChainingHashTable<>(10);
        //进行插入操作
        for (int i = 0; i < arr.length; i ++){
            separateChainingHashTable.insert(arr[i]);
        }
        //打印链表
        separateChainingHashTable.printHashTable();
    }

运行结果如下：

current position is : 0
0
current position is : 1
81
1
current position is : 4
64
4
current position is : 5
25
current position is : 6
36
16
current position is : 9
49
9

separate chaning.png

当然除了插入默认的基本类型，我们还可以插入对象，但一定要重定义对象的equals()和hashCode()方法

public class Employee {
    private String name;
    private double salary;
    private int seniority;
    //构造函数
    public Employee(String name, double salary, int seniority){
        this.name = name;
        this.salary = salary;
        this.seniority = seniority;
    }
    //判断对象是否相同
    public boolean equals(Object rhs){
        //满足为Employee类型且名字相同
        return rhs instanceof Employee && name.equals(((Employee) rhs).name);
    }
    //重写hashCode
    public int hashCode(){
        return name.hashCode();
    }
    //打印对象
    @Override
    public String toString() {
        return "name: " + name + " salary: " + salary + " seniority: " + seniority + "\n";
    }
}
public static void main(String[] args){
        SeparateChainingHashTable<Employee> hashTable = new SeparateChainingHashTable<>(11);
        hashTable.insert(new Employee("worker", 1000,3));
        hashTable.insert(new Employee("worker", 1500,3));
        hashTable.insert(new Employee("worker", 1600,3));
        hashTable.insert(new Employee("Manager", 2000, 2));
        hashTable.insert(new Employee("Manager", 2500, 2));
        hashTable.insert(new Employee("boss", 3000, 1));
        hashTable.printHashTable();
    }

结果如下：

current position is : 6
name: Manager salary: 2000.0 seniority: 2
current position is : 7
name: boss salary: 3000.0 seniority: 1
current position is : 10
name: worker salary: 1000.0 seniority: 3

我们可以看到对于name相同的对象是不会重复插入的。

完整代码：

public class SeparateChainingHashTable<AnyType> {

    public SeparateChainingHashTable(){
        this(DEFAULT_TABLE_SIZE);
    }

    //进行初始化操作
    public SeparateChainingHashTable(int size){
        //初始化表，这里调用了一个nextPrime函数，以保证其表的大小为素数
        theLists = new LinkedList[nextPrime(size)];
        //初始化表中的链表
        for (int i = 0; i < theLists.length; i ++){
            theLists[i] = new LinkedList<AnyType>();
        }
    }

    public void insert(AnyType x){
        //获取x根据hash后找到所对应的位置
        List<AnyType> whichList = theLists[myHash(x)];
        //如果当前位置链表不包含元素，则进行插入操作
        if (!whichList.contains(x)){
            //进行添加
            whichList.add(x);
            //判断是否达到表的长度，若达到则进行rehash操作，以扩大表的大小
            if (++ currentSize > theLists.length){
                rehash();
            }
        }
    }
    //删除操作
    public void remove(AnyType x){
        //获取到对应位置的链表
        List<AnyType> whichList = theLists[myHash(x)];
        //检查是否包含元素，包含则进行删除操作，并大小--
        if (whichList.contains(x)){
            whichList.remove(x);
            currentSize --;
        }
    }

    //检查是否包含某个元素
    public boolean contains(AnyType x){
        List<AnyType> whichList = theLists[myHash(x)];
        return whichList.contains(x);
    }

    public void makeEmpty(){
        for (int i = 0; i < theLists.length; i ++){
            theLists[i].clear();
        }
    }

    //定义默认表的大小
    private static final int DEFAULT_TABLE_SIZE = 101;
    //定义表的存储
    private List<AnyType>[] theLists;
    //定义表当前的大小
    private int currentSize;

    //根据值获取到其对应的hash位置
    private int myHash(AnyType x){
        int hashVal = x.hashCode();
        hashVal %= theLists.length;
        //考虑到负数的情况
        if (hashVal < 0){
            hashVal += theLists.length;
        }
        return hashVal;
    }

    private void rehash(){
        //获取到原来的表
        List<AnyType>[] oldLists = theLists;
        //对现有的表大小进行扩大
        theLists = new List[nextPrime(2 * theLists.length)];
        //初始化新表
        for (int j = 0; j < theLists.length; j ++){
            theLists[j] = new LinkedList<AnyType>();
        }
        //初始化大小
        currentSize = 0;
        //将旧表中的数据重新插入到新表中
        for (int i = 0; i < oldLists.length; i ++){
            for (AnyType item : oldLists[i]){
                insert(item);
            }
        }
    }

    //返回下一个素数
    private static int nextPrime(int n){
        while (!isPrime(n)){
            n ++;
        }
        return n;
    }
    //判断是否为素数
    private static boolean isPrime(int n){
        for (int i = 2; i <= Math.sqrt(n); i ++){
            if (n % i == 0 && n != 2){
                return false;
            }
        }
        return true;
    }

    //打印链表结构
    public void printHashTable(){
        for (int i = 0; i < theLists.length; i ++){
            if (theLists[i] != null && theLists[i].size() > 0){
                System.out.println("current position is : " + i );
                for (AnyType x : theLists[i]){
                    System.out.println(x);
                }
            }
        }
    }
}

散列（一）

定义：

散列函数：

解决冲突的两种方法：

完整代码：

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

Java_集合

Java学习笔记