哈希查找

学习“五大经典查找”(2)

博客分类：
• 查找

java 算法 jdk 数据结构  

大家可否知道，其实查找中有一种O(1)的查找，即所谓的秒杀。

第三：哈希查找：
     对的，他就是哈希查找，说到哈希，大家肯定要提到哈希函数，呵呵，这东西已经在我们脑子里面形成固有思维了。大家一定要知道“哈希“中的对应关系。

     比如说： ”5“是一个要保存的数，然后我丢给哈希函数，哈希函数给我返回一个”2"，那么此时的”5“和“2”就建立一种对应关系，这种关系就是所谓的“哈希关系”，在实际应用中也就形成了”2“是key，”5“是value。

    那么有的朋友就会问如何做哈希，首先做哈希必须要遵守两点原则：
          ①:  key尽可能的分散，也就是我丢一个“6”和“5”给你，你都返回一个“2”，那么这样的哈希函数不尽完美。
          ②： 哈希函数尽可能的简单，也就是说丢一个“6”给你，你哈希函数要搞1小时才能给我，这样也是不好的。

其实常用的做哈希的手法有“五种”：

第一种：”直接定址法“。
很容易理解，key=Value+C； 这个“C"是常量。Value+C其实就是一个简单的哈希函数。

第二种：“除法取余法”。
很容易理解， key=value%C;解释同上。

第三种：“数字分析法”。
  这种蛮有意思，比如有一组value1=112233，value2=112633，value3=119033，
针对这样的数我们分析数中间两个数比较波动，其他数不变。那么我们取key的值就可以是
   key1=22,key2=26,key3=90。

第四种：“平方取中法”。此处忽略，见名识意。

第五种：“折叠法”。
   这种蛮有意思,比如value=135790，要求key是2位数的散列值。那么我们将value变为13+57+90=160，   然后去掉高位“1”,此时key=60，哈哈，这就是他们的哈希关系，这样做的目的就是key与每一位value都相关，来做到“散列地址”尽可能分散的 目地。

    正所谓常在河边走，哪有不湿鞋。哈希也一样，你哈希函数设计的再好，搞不好哪一次就撞楼了，那么抛给我们的问题就是如果来解决“散列地址“的冲突。

其实解决冲突常用的手法也就2种：

第一种： “开放地址法“。
所谓”开放地址“，其实就是数组中未使用的地址。也就是说，在发生冲突的地方，后到的那个元素（可采用两种方式
:①线性探测，②函数探测）向数组后寻找"开放地址“然后把自己插进入。

第二种：”链接法“。
  这个大家暂时不懂也没关系，我就先介绍一下原理，就是在每个元素上放一个”指针域“，在发生冲突的地方，后到的那个元素将自己的数据域抛给冲突中的元素，此时冲突的地方就形成了一个链表。

  上面啰嗦了那么多，也就是想让大家在”设计哈希“和”解决冲突“这两个方面提一点参考和手段。

那么下面就上代码了，
     设计函数采用：”除法取余法“。
     冲突方面采用:”开放地址线性探测法"。

import
 java.util.List;
import
 java.util.Arrays;
import
 java.util.Scanner;
public
 
class
 HashProgram
     {
         //“除法取余法”
         static
 
int
 hashLength = 
13
;

         //原数据
          static
 Integer a[]={ 
13
, 
29
, 
27
, 
28
, 
26
, 
30
, 
38
 };
          static
 List<Integer> list=Arrays.asList(a);

         //c#中可以这样啊！jdk1.7也不能啊
        // static List<int> list = new List<int>() { 13, 29, 27, 28, 26, 30, 38 };

         //哈希表长度
         static
 
int
[] hash = 
new
 
int
[hashLength];

       public
 
static
 
void
 main(String[] args)
         {
             Scanner sca=new
 Scanner(System.in);
             //创建hash
             for
 (
int
 i = 
0
; i < list.size(); i++)
             {
                 InsertHash(hash, hashLength, list.get(i));
             }

             System.out.println("Hash表中的数据："
);
             for
(
int
 i:hash)
               System.out.print(i+","
);

             while
 (
true
)
             {
                 System.out.printf("\n请输入要查找数字："
);
                 int
 result = sca.nextInt();
                 int
  index = SearchHash(hash, hashLength, result);

                 if
 (index != -
1
)
                   System.out.println("数字"
 + result + 
"在索引的位置是:"
 + index);
                 else
                   System.out.println("呜呜，"
 + result + 
" 在hash中没有找到！"
);

             }
         }


 // Hash表检索数据

     static
 
int
 SearchHash(
int
[] hash, 
int
 hashLength, 
int
 key)
         {
             //哈希函数
             int
 hashAddress = key % hashLength;

             //指定hashAdrress对应值存在但不是关键值，则用开放寻址法解决
             while
 (hash[hashAddress] != 
0
 && hash[hashAddress] != key)
             {
                 hashAddress = (++hashAddress) % hashLength;
             }

             //查找到了开放单元，表示查找失败
             if
 (hash[hashAddress] == 
0
)
                 return
 -
1
;
             return
 hashAddress;

         }


 //数据插入Hash表

         static
 
void
 InsertHash(
int
[] hash, 
int
 hashLength, 
int
 data)
         {
             //哈希函数
             int
 hashAddress = data % 
13
;
              //如果key存在，则说明已经被别人占用，此时必须解决冲突
             while
 (hash[hashAddress] != 
0
)
             {
                 //用开放寻址法找到
                 hashAddress = (++hashAddress) % hashLength;
             }

             //将data存入字典中
             hash[hashAddress] = data;
         }

 }

运行：
D:\java>java   HashProgram
Hash表中的数据：
13,27,28,29,26,30,0,0,0,0,0,0,38
请输入要查找数字：38
数字38在索引的位置是:12

请输入要查找数字：33
呜呜，33 在hash中没有找到！

请输入要查找数字：27
数字27在索引的位置是:1

请输入要查找数字：

第四：索引查找
　　简称分级查找．例如汉字查找．对象是计算机为索引查找而建立的主表和各级索引表，主表只有一个，索引表的级数和数量不受限制，根据具体的需要确定．索引存储结构是数据组织的一项很重要的存储技术，在数据库领域中有广泛的应用．

　　基本思想：首先把一个集合或线性表（主表）按照一定的函数关系或条件划分成若干个逻辑上的子表，为每个子表分别建立一个索引项，由所有这些索引项构成主表的一个索引表，然后，可采用顺序或是链接的方式来存储索引表和每个子表．

索引表包含三个域：
（1）索引值域，用来存储对应子表的索引值，相当于记录的关键字，在索引表中由此索引值来唯一标识一个索引项．

（2）表的开始位置域，用来存储对应子表的第一个元素的存储位置，从此位置出发可以依次访问到子表中的所有元素．

（3）子表的长度域：用来存储对应子表的元素个数．

　　索引查找算法：是在索引表和主表上进行的查找．过程是：首先根据给定的索引值Ｋ１，在索引表上查找出索引值等于Ｋ１的索引项，以确定对应子表 在主表的开始位置和长度．然后再根据给定的关键字Ｋ２，在对应的子表中查找出关键字等于Ｋ２的元素．对索引表或子表的查找时，若表是顺序存储的有序表，则 可进行顺序查找，也可以进行二分查找．否则只能进行顺序查找．

import
 java.util.Arrays;
public
 
class
 IndexSearch {

    // 主表
    static
 
int
[] students = { 
101
, 
102
, 
103
, 
104
, 
105
, 
0
, 
0
, 
0
, 
0
, 
0
, 
201
, 
202
,
            203
, 
204
, 
0
, 
0
, 
0
, 
0
, 
0
, 
0
, 
301
, 
302
, 
303
, 
0
, 
0
, 
0
, 
0
, 
0
, 
0
, 
0
 };
    // 索引表
    static
 IndexItem[] indexItem = { 
new
 IndexItem(
1
, 
0
, 
5
),
            new
 IndexItem(
2
, 
10
, 
4
), 
new
 IndexItem(
3
, 
20
, 
3
), };

    // 查找数据
    public
 
static
 
int
 indexSearch(
int
 key) {
        IndexItem item = null
;

        // 建立索引规则
        int
 index = key / 
100
;

        // 首先去索引找
        for
 (
int
 i = 
0
; i < indexItem.length; i++) {
            if
 (indexItem[i].index == index) {
                item = indexItem[i];
                break
;
            }
        }

        // 如果item为null，则说明在索引中查找失败
        if
 (item == 
null
)
            return
 -
1
;

        for
 (
int
 i = item.start; i < item.start + item.length; i++) {
            if
 (students[i] == key) {
                return
 i;
            }
        }
        return
 -
1
;
    }

    // / 插入数据
    public
 
static
 
int
 insert(
int
 key) {
        IndexItem item = null
;
        // 建立索引规则
        int
 index = key / 
100
;
        int
 i = 
0
;
        for
 (i = 
0
; i < indexItem.length; i++) {
            // 获取到了索引
            if
 (indexItem[i].index == index) {
                item = indexItem[i];
                break
;
            }
        }
        if
 (item == 
null
)
            return
 -
1
;
        // 更新主表
        students[item.start + item.length] = key;
        // 更新索引表
        indexItem[i].length++;
        return
 
1
;
    }

    public
 
static
 
void
 main(String[] args) {
        int
 value = 
205
;
        // 将205插入集合中，过索引
        int
 index = insert(value);
        insert(308
);

        // 如果插入成功，获取205元素所在的位置
        if
 (index == 
1
) {
            System.out.println("\n插入后数据："
 + Arrays.toString(students));
            System.out.println("\n数据元素：205在数组中的位置为 "
 + indexSearch(
205
) + 
"位"
);
        }

    }

}

// 索引项实体
class
 IndexItem {
    // 对应主表的值
    public
 
int
 index;
    // 主表记录区间段的开始位置
    public
 
int
 start;
    // 主表记录区间段的长度
    public
 
int
 length;

    public
 IndexItem() {
    }

    public
 IndexItem(
int
 index, 
int
 start, 
int
 length) {
        this
.index = index;
        this
.start = start;
        this
.length = length;
    }
}

运行：
D:\java>java   IndexSearch

插入后数据：[101, 102, 103, 104, 105, 0, 0, 0, 0, 0, 201, 202, 203, 204, 205, 0, 0, 0, 0, 0, 301, 302, 303, 308, 0, 0, 0, 0, 0, 0]

数据元素：205在数组中的位置为 14位