我的java学习-哈希函数和哈希表

没有学习数据结构之前，一直都知道有哈希函数和哈希表，就是不知道为什么每次大家在应聘和求职的面试文章里经常会提到这个哈希表的问题。
哈希表方法和其他查找方法不同的地方，在于线性查找、二分查找、分块查找这些方法，都是对关键字进行多次比较判断，来确定集合里是否存在某个关键字，这样查找的办法显然存在 一定的浪费，而且在数据量大的时候效率低下时间长。哈希表是用计算的方法来确定集合里是否存在某关键字，多次重复的比较和一次计算，显然，是计算的方法效率更高。
哈希函数就是将散列没有规律的关键字转化成一个偏移地址的关键所在，但是哈希函数会产生一定的冲突，这时候，不是说哈希表方法效率会降低，可以用链表法或者双重哈希法解决冲突。哈希函数对于网络上大量的数据搜索响应，显然是一个好的解决方法，java主要适用于网络和数据管理有关，当然在java面试里哈希函数是必然要提到的。

class HashTableSearch{  //哈希表搜索
    private static class Node{  //用链表法解决哈希冲突
        int key;
        Node next;
    }
    
    public boolean HashSearch(int[] data, int key){  //判断data数组里面是否有某个关键字
        int p = 1;
        for(int i = data.length ; i > 1; i --){
            if(isPrimes(i)){    //在data长度下标里面选择一个最接近表长度的质数
                p = i;
                break;
            }
        }
        Node[] hashtable = createHashTable(data, p);  //用质数p做参考新建一个hash表
        int k = key % p;            //这里的hash算法与建表的算法一致
        Node cur = hashtable[k];    //直接取hash表里面k位置数据建立结点
        while(cur != null && cur.key != key){  //当前位置已经有数据并且不等于key值
            cur = cur.next;         //链表数据移动到cur的下一位，对比和搜索
        }
        if(cur == null)    //如果k值对应hash表里空值，表示没有找到元素，失败的访问时间短为常量
            return false;
        else 
            return true;
    }
    
    public Node[] createHashTable(int[] data, int p){  //哈希表建表方法
        Node[] hashtable = new Node[p];
        int k;
        for(int i = 0; i < data.length; i ++){
            Node node = new Node();  //新建一个结点
            node.key = data[i];     //结点数据等于当前data数组里某值
            node.next = null;       //结点后继为空
            k = data[i] % p;        //计算数据对应的hash值
            if(hashtable[k] == null){   //如果表里面k位置是空，将新建结点赋值给hash表
                hashtable[k] = node;
            }else{
                Node cur = hashtable[k];  //新建一个结点指向hash表里面k结点
                while(cur.next != null){    //找到k结点位置最后一个cur位
                    cur = cur.next;
                }
                cur.next = node;  //将当前结点作为k位置最后一个结点添加到hash表
            }
        }
        return hashtable;
    }
    
    public boolean isPrimes(int n){  //检查是否是质数
        for(int i = 2; i <= Math.sqrt(n); i++){
            if(n % i == 0){
                return false;
            }
        }
        return true;
    }
}