基于Hash的查找算法实现

package da;

public class MyMap< K, V> {
    private int size;// 当前容量
    private static int INIT_CAPACITY = 16;// 默认容量
    private Entry< K, V>[] container;// 实际存储数据的数组对象
    private static float LOAD_FACTOR = 0.75f;// 装载因子
    private int max;// 能存的最大的数=capacity*factor   

    // 自己设置容量和装载因子的构造器
    public MyMap(int init_Capaticy, float load_factor) {
        if (init_Capaticy < 0)
            throw new IllegalArgumentException("Illegal initial capacity: "
                    + init_Capaticy);
        if (load_factor <= 0 || Float.isNaN(load_factor))
            throw new IllegalArgumentException("Illegal load factor: "  + load_factor);
        this.LOAD_FACTOR = load_factor;
        max = (int) (init_Capaticy * load_factor);
        container = new Entry[init_Capaticy];
    }   

    // 使用默认参数的构造器
    public MyMap() {
        this(INIT_CAPACITY, LOAD_FACTOR);
    }   

    /**
     * 存
     *
     * @param k
     * @param v
     * @return
     */
    public boolean put(K k, V v) {
        // 1.计算K的hash值
        // 因为自己很难写出对不同的类型都适用的Hash算法，故调用JDK给出的hashCode()方法来计算hash值
        int hash = k.hashCode();
        //将所有信息封装为一个Entry
        Entry< K,V> temp=new Entry(k,v,hash);
            if(setEntry(temp, container)){
                // 大小加一
                size++;
                return true;
            }
            return false;
    }   

    /**
     * 扩容的方法
     *
     * @param newSize
     *            新的容器大小
     */
    private void reSize(int newSize) {
        // 1.声明新数组
        Entry< K, V>[] newTable = new Entry[newSize];
        max = (int) (newSize * LOAD_FACTOR);
        // 2.复制已有元素,即遍历所有元素，每个元素再存一遍
        for (int j = 0; j < container.length; j++) {
            Entry< K, V> entry = container[j];
            //因为每个数组元素其实为链表，所以…………
            while (null != entry) {
                setEntry(entry, newTable);
                entry = entry.next;
            }
        }
        // 3.改变指向
        container = newTable;   

    }   

    /**
     *将指定的结点temp添加到指定的hash表table当中
     * 添加时判断该结点是否已经存在
     * 如果已经存在，返回false
     * 添加成功返回true
     * @param temp
     * @param table
     * @return
     */
    private boolean setEntry(Entry< K,V> temp,Entry[] table){
        // 根据hash值找到下标
        int index = indexFor(temp.hash, table.length);
        //根据下标找到对应元素
        Entry< K, V> entry = table[index];
        // 3.若存在
        if (null != entry) {
            // 3.1遍历整个链表，判断是否相等
            while (null != entry) {
                //判断相等的条件时应该注意，除了比较地址相同外，引用传递的相等用equals()方法比较
                //相等则不存，返回false
             if ((temp.key == entry.key||temp.key.equals(entry.key)) &&
 temp.hash == entry.hash&&(temp.value==entry.value||temp.value.equals(entry.value))) {
                    return false;
                }  

                 else if(temp.key == entry.key && temp.value != entry.value) {
                     entry.value = temp.value;
                    return true;
                } 

                //不相等则比较下一个元素
                else if (temp.key != entry.key) {
                        //到达队尾，中断循环
                        if(null==entry.next){
                            break;
                        }
                        // 没有到达队尾，继续遍历下一个元素
                        entry = entry.next;
                }
            }
            // 3.2当遍历到了队尾，如果都没有相同的元素，则将该元素挂在队尾
            addEntry2Last(entry,temp);
               return true;
        }
        // 4.若不存在,直接设置初始化元素
        setFirstEntry(temp,index,table);
        return true;
    }   

    private void addEntry2Last(Entry< K, V> entry, Entry< K, V> temp) {
        if (size > max) {
            reSize(container.length * 4);
        }
        entry.next=temp;   

    }   

    /**
     * 将指定结点temp，添加到指定的hash表table的指定下标index中
     * @param temp
     * @param index
     * @param table
     */
    private void setFirstEntry(Entry< K, V> temp, int index, Entry[] table) {
        // 1.判断当前容量是否超标，如果超标，调用扩容方法
        if (size > max) {
            reSize(table.length * 4);
        }
        // 2.不超标，或者扩容以后，设置元素
        table[index] = temp;
        //！！！！！！！！！！！！！！！
        //因为每次设置后都是新的链表，需要将其后接的结点都去掉
         //NND，少这一行代码卡了哥哥7个小时（代码重构）
        temp.next=null;
    }   

    /**
     * 取
     *
     * @param k
     * @return
     */
    public V get(K k) {
        Entry< K, V> entry = null;
        // 1.计算K的hash值
        int hash = k.hashCode();
        // 2.根据hash值找到下标
        int index = indexFor(hash, container.length);
        // 3。根据index找到链表
        entry = container[index];
        // 3。若链表为空，返回null
        if (null == entry) {
            return null;
        }
        // 4。若不为空，遍历链表，比较k是否相等,如果k相等，则返回该value
        while (null != entry) {
            if (k == entry.key||entry.key.equals(k)) {
                return entry.value;
            }
            entry = entry.next;
        }
        // 如果遍历完了不相等，则返回空
        return null;   

    }   

    /**
     * 根据hash码，容器数组的长度,计算该哈希码在容器数组中的下标值
     *
     * @param hashcode
     * @param containerLength
     * @return
     */
    public int indexFor(int hashcode, int containerLength) {
        return hashcode & (containerLength - 1);   

    }   

    /**
     * 用来实际保存数据的内部类,因为采用挂链法解决冲突，此内部类设计为链表形式
     *
     * @param < K>key
     * @param < V>
     *            value
     */
    class Entry< K, V> {
        Entry< K, V> next;// 下一个结点
        K key;// key
        V value;// value
        int hash;// 这个key对应的hash码，作为一个成员变量，当下次需要用的时候可以不用重新计算   

        // 构造方法
        Entry(K k, V v, int hash) {
            this.key = k;
            this.value = v;
            this.hash = hash;   

        }   

        //相应的getter()方法   

    }
}

package da;

public class Main {
public static void main(String[] args) {   
MyMap< String, String> mm = new MyMap< String, String>();    

Long aBeginTime=System.currentTimeMillis();//记录BeginTime   

for(int i=0;i< 1000000;i++){   
mm.put(""+i, ""+i*100);   
}   

Long aEndTime=System.currentTimeMillis();//记录EndTime   
System.out.println("insert time-->"+(aEndTime-aBeginTime));   

Long lBeginTime=System.currentTimeMillis();//记录BeginTime   
mm.get(""+100000);   

Long lEndTime=System.currentTimeMillis();//记录EndTime   
System.out.println("seach time--->"+(lEndTime-lBeginTime));   
}   

}

package da;

import java.util.Random;

public class Main {
public static void main(String[] args) {   
MyMap< String, String> mm = new MyMap< String, String>();    

Long aBeginTime=System.currentTimeMillis();//记录BeginTime   

String a[]={"李锦根","金行","成龙","客户"};

for(int i=0;i< 1000000;i++){   
Random s=new Random();
//int temp=s.nextInt();
   int temp=(int) ((Math.random() * 3 + 1) * 1);
mm.put(""+i, ""+a[temp]); 
//mm.put(""+100000000+i,""+"金"); 
System.out.println(i+a[temp]);
} 
mm.put(""+100000000,""+"金"); 
Long aEndTime=System.currentTimeMillis();//记录EndTime   
System.out.println("insert time-->"+(aEndTime-aBeginTime));   

Long lBeginTime=System.currentTimeMillis();//记录BeginTime   
//mm.get(""+3+a[0]);   
//System.out.println(mm.get(""+100));
int coun=0;
for(int i=1;i< 1000000;i++){
//System.out.println(mm.get(""+i));
if(mm.get(""+i)!=null&&mm.get(""+i).equals("金行")){
coun++;
}
}
System.out.println(coun);
Long lEndTime=System.currentTimeMillis();//记录EndTime   
System.out.println("seach time--->"+(lEndTime-lBeginTime));   
}   
}

999958成龙
999959成龙
999960客户
999961成龙
999962成龙
999963金行
999964成龙
999965成龙
999966金行
999967金行
999968成龙
999969金行
999970客户
999971金行
999972成龙
999973客户
999974成龙
999975客户
999976客户
999977金行
999978客户
999979成龙
999980成龙
999981金行
999982客户
999983成龙
999984成龙
999985客户
999986成龙
999987金行
999988金行
999989客户
999990金行
999991客户
999992金行
999993金行
999994金行
999995成龙
999996客户
999997成龙
999998金行
999999金行
insert time-->11621
219770
seach time--->430


探讨Hash表中的一些原理/概念，及根据这些原理/概念，自己设计一个用来存放/查找数据的Hash表，并且与JDK中的HashMap类进行比较。

我们分一下七个步骤来进行。 
一。 Hash表概念
二 . Hash构造函数的方法，及适用范围
三. Hash处理冲突方法，各自特征
四. Hash查找过程
五. 实现一个使用Hash存数据的场景--Hash查找算法，插入算法
六. JDK中HashMap的实现
七. Hash表与HashMap的对比，性能分析

一。 Hash表概念 
   在Hash表中，记录在表中的位置和其关键字之间存在着一种确定的关系。这样 我们就能预先知道所查关键字在表中的位置，从而直接通过下标找到记录。

1) 哈希(Hash)函数是一个映象，即： 将关键字的集合映射到某个地址集合上，它的设置很灵活，
只要这个地址集合的大小不超出允许范围即可；

2) 由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，
即： key1!=key2，而 f (key1) = f(key2)。

3). 只能尽量减少冲突而不能完全避免冲突，这是因为通常关键字集合比较大，其元素包括所有可能的关键字，
而地址集合的元素仅为哈希表中的地址值.在构造这种特殊的“查找表” 时，除了需要选择一个“好”(尽可能少产生冲突)
的哈希函数之外；还需要找到一 种“处理冲突” 的方法。

二 . Hash构造函数的方法，及适用范围

直接定址法 
数字分析法 
平方取中法 
折叠法 
除留余数法 
随机数法 

（1）直接定址法：

哈希函数为关键字的线性函数，H(key) = key 或者 H(key) = a * key + b

（2）数字分析法：
    假设关键字集合中的每个关键字都是由 s 位数字组成 (u1, u2, …, us)，分析关键字集中的全体， 
并从中提取分布均匀的若干位或它们的组合作为地址。

此法适于:能预先估计出全体关键字的每一位上各种数字出现的频度。

（3）平方取中法：
   以关键字的平方值的中间几位作为存储地址。求“关键字的平方值” 的目的是“扩大差别” ，
同 时平方值的中间各位又能受到整个关键字中各位的影响。

（4）折叠法：
    将关键字分割成若干部分，然后取它们的叠加和为哈希地址。两种叠加处理的方法：移位叠加:
将分割后的几部分低位对齐相加；间界叠加:从一端沿分割界来回折叠，然后对齐相加。

此法适于：关键字的数字位数特别多。

（5）除留余数法：

设定哈希函数为:H(key) = key MOD p ( p≤m )，其中， m为表长，p 为不大于 m 的素数，或 是不含 20 以下的质因子

（6）随机数法：

设定哈希函数为:H(key) = Random(key)其中，Random 为伪随机函数

   实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，
以及哈希表长度（哈希地址范围），总的原则是使产生冲突的可能性降到尽可能地小。

三. Hash处理冲突方法，各自特征

   “处理冲突” 的实际含义是：为产生冲突的关键字寻找下一个哈希地址。

开放定址法 
再哈希法 
链地址法

（1）开放定址法：
    为产生冲突的关键字地址 H(key) 求得一个地址序列： H0, H1, H2, …, Hs 1≤s≤m-1，Hi = ( H(key) +di ) MOD m，
其中： i=1, 2, …, s，H(key)为哈希函数;m为哈希表长;

（2）链地址法：

将所有哈希地址相同的记录都链接在同一链表中。

（3）再哈希法：
   方法：构造若干个哈希函数，当发生冲突时，根据另一个哈希函数计算下一个哈希地址，直到冲突不再发 生。
即：Hi=Rhi(key) i=1,2,……k，其中：Rhi——不同的哈希函数，特点：计算时间增加

四. Hash查找过程

    对于给定值 K,计算哈希地址 i = H(K)，若 r[i] = NULL 则查找不成功，若 r[i].key = K 则查找成功， 
否则 “求 下一地址 Hi” ，直至r[Hi] = NULL (查找不成功) 或r[Hi].key = K (查找成功) 为止。

五. 实现一个使用Hash存数据的场景-------Hash查找算法，插入算法

    假设我们要设计的是一个用来保存中南大学所有在校学生个人信息的数据表。因为在校学生数量也不是特别巨大(8W)，
每个学生的学号是唯一的,因此，我们可以简单的应用直接定址法，声明一个10W大小的数组，每个学生的学号作为主键。
然后每次要添加或者查找学生，只需要根据需要去操作即可。

   但是，显然这样做是很脑残的。这样做系统的可拓展性和复用性就非常差了，比如有一天人数超过10W了？
如果是用来保存别的数据呢？或者我只需要保存20条记录呢？声明大小为10W的数组显然是太浪费了的。

   如果我们是用来保存大数据量（比如银行的用户数，4大的用户数都应该有3-5亿了吧？），这时候我们计算出来的
HashCode就很可能会有冲突了， 我们的系统应该有“处理冲突”的能力，此处我们通过挂链法“处理冲突”。

  如果我们的数据量非常巨大，并且还持续在增加，如果我们仅仅只是通过挂链法来处理冲突，可能我们的链上挂了
上万个数据后，这个时候再通过静态搜索来查找链表，显然性能也是非常低的。所以我们的系统应该还能实现自动扩容，
当容量达到某比例后，即自动扩容，使装载因子保存在一个固定的水平上。

综上所述，我们对这个Hash容器的基本要求应该有如下几点：

满足Hash表的查找要求（废话）
能支持从小数据量到大数据量的自动转变（自动扩容）
使用挂链法解决冲突

时间： 2024-09-25 09:45:46

基于Hash的查找算法实现的相关文章

基于Hash算法的高维数据的最近邻检索

一.摘要 最紧邻检索:一种树基于树结构,一种是基于hash a.随机投影算法,需要产生很多哈希表,才能提高性能. b.基于学习的哈希算法在哈希编码较短时候性能不错,但是增加编码长度并不能显著提高性能. 随机投影:实际上就是随机的,实际上需要挖掘使用数据的内部结构,结合最大熵原理. 基于密度的哈希就是依据数据分布产生最合理的投影. 数据稀疏:稀疏编码+ 压缩感知 GIST1M数据集2.55G,这个是专门做最近邻检索的. 二.绪论 2.1 课题背景 最近邻检索的主要问题是如何建立高效索引. 数据集是

Java 查找算法

这个问题有几个点要先确认 必须是有序,如果无序的话就只能全遍历了 查找算法跟数据结构相关,不同的数据结构适用于不同的查找算法 查找算法与磁盘I/O有一定的关系,比如数据库在索引排序的时候,如果每次都从磁盘读取一个节点然后进行判断 数组 如果知道下标的话就方便了,查找的复杂度为1. 如果是针对值的查找,那么顺序遍历是O(n), 二分查找 使用二分查找的话可以减少时间复杂度为:O(logn) /** * 二分查找又称折半查找,它是一种效率较高的查找方法. [二分查找要求]:1.必须采用顺序存储结构

[算法系列之十三]Rabin-Karp字符串查找算法

简介 蛮力匹配法(brute force string matching)是字符串匹配算法中最基本的一种,也是最简单的一种.它确实有自己的优点,比如它并不需要对文本串(text)或模式串(pattern)进行预处理.然而它最大的问题就是运行速度太慢,所以在很多场合下蛮力字符串匹配算法并不是那么有用.我们需要一些更快的方法来完成字符串的匹配工作,然而在此之前,我们还是回过头来再看一遍蛮力匹配法,以便更好地理解其他子串匹配算法. 如下图所示,在蛮力字符串匹配里,我们将文本中的每一个字符和模式串的第一

二分查找算法及其变种

前言 二分查找算法也称为折半查找算法,是一种在查找算法中普遍使用的算法.其算法的基本思想是:在有序表中,取中间的记录作为比较关键字,若给定值与中间记录的关键字相等,则查找成功:若给定的值小于中间记录的关键字,则在中间记录的左半区间继续查找:若给定值大于中间记录的关键字,则在中间记录的右半区间继续查找:不断重复这个过程,直到查找成功.否则查找失败.这个思想与孔子中的中庸思想和相似. 二分查找算法的实现 基于上述的思想,可以很快写出如下代码: public int binarySearch(int[

语言-数据结构查找算法比较研究

问题描述 数据结构查找算法比较研究 谁有用C语言实现多种查找算法的代码啊,里面可以显示查找时间和查找次数的.. 解决方案 自己写一个就是了. 线性查找,复杂度O(N) 折半查找,复杂度O(LogN) Hash查找,复杂度O(1)

[算法]二分查找算法

[思想] 二分搜索主要解决的问题是确定排序后的数组x[0,n-1]中是否包含目标元素target. 二分搜索通过持续跟踪数组中包含元素target的范围(如果target存在数组中的话)来解决问题. 一开始,这个范围是整个数组,然后通过将target与数组中的中间项进行比较并抛弃一半的范围来缩小范围.该过程持续进行, 直到在数组中找到target或确定包含target的范围为空时为止.在有n个元素的表中,二分搜索大约需要执行lgn次比较操作. 提供充足的时间,竟然只有10%的专业程序员能够将这个

Python实现二分查找算法实例

  本文实例讲述了Python实现二分查找算法的方法.分享给大家供大家参考.具体实现方法如下: ? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #!/usr/bin/env python import sys def search2(a,m): low = 0 high = len(a) - 1 while(low <= high): mid = (low + high)/2 midval = a[mid] if midval <

使用PHP实现二分查找算法代码分享

第一种方法: [二分查找要求]:1.必须采用顺序存储结构 2.必须按关键字大小有序排列. [优缺点]折半查找法的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难.因此,折半查找方法适用于不经常变动而查找频繁的有序列表. [算法思想]首先,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功:否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表. 复制代码 代码如下: <?

Java实现二分法查找算法

[ 什么是二分查找 ] 二分查找又称为折半查找,该算法的思想是将数列按序排列,采用跳跃式方法进行查找,即先以有序数列的中点位置为比较对象, 如果要找的元素值小于该中点元素,则将待查序列缩小为左半部分,否则为右半部分.以此类推不断缩小搜索范围. [ 二分查找的条件 ] 二分查找的先决条件是查找的数列必须是有序的. [ 二分查找的优缺点 ] 优点:比较次数少,查找速度快,平均性能好: 缺点:要求待查数列为有序,且插入删除困难: 适用场景:不经常变动而查找频繁的有序列表. [ 算法步骤描述 ] ① 首