剑指OfferP41与哈希散列

数组中重复的数字

思路1：排序，然后比较当前个与下一个是否相同，相同则为重复元素。

思路2：一遍遍历，hash表将数组元素存起来，每次判断是否在hash里出现过。t:O(n)，space: O(n)

思路3：题目限制得比较死，数字在0~n-1的范围。所以可以采取书中的特殊交换解法。交换有限次即可找到，因此time O(n)。

#include <stdio.h>
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

// solution2
vector<int> duplicate2(int numbers[],int length){
    vector<int> duplication;
    unordered_map<int,int> mmap;
    if (numbers==nullptr || length<=0) {
        return duplication;
    }
    for (int i=0; i<length; i++) {
        // 可以去除这个限制了
        if (numbers[i] < 0 || numbers[i] > length+1) {
            return duplication;
        }
        if (mmap.find(numbers[i]) != mmap.end() ) {
            duplication.push_back(numbers[i]);
        }
        else{
            mmap[i] = numbers[i];
        }
    }
    return duplication;
}

// solution 3
vector<int> duplicate(int numbers[],int length){
    vector<int> duplication;
    // Boundary conditions
    if (numbers==nullptr || length <=0) {
        return duplication;
    }
    for (int i=0; i<length; i++) {
        if (numbers[i] < 0 || numbers[i] > length-1) {
            return duplication;
        }
    }
    for (int i=0; i<length; i++) {
        while (numbers[i] != i) {
            if (numbers[i] == numbers[numbers[i]]) {
                duplication.push_back(numbers[i]);
                break;
            }
            //swap num[i] and num[num[i]]
            swap(numbers[i], numbers[numbers[i]]);
        }
    }
    return duplication;
}

int main(){
    // 测试输出重复的数字 the duplicate num
    int num[7] = {2,3,1,0,2,5,3};
    vector<int> duplication;
    duplication = duplicate(num, sizeof(num)/sizeof(int));
    for(auto item:duplication) cout<<item<<endl;
    return 0;
}

我修改了下，直接返回vector重复的数字。

hash原理

根据关键码值直接访问表。如可以把关键码值映射到数组中的位置来访问记录，这个就是散列。把关键码值映射到位置的函数称为散列函数，用h表示。存放记录的数组称为散列表 HT。散列表中的第一个位置称为槽 slot，HT中槽的数目用M表示。$i = h(K)$ 是表中满足 $0 \leq h(K) < M$ 的一个槽，记录在HT[i] 的关键码值与K相等。

散列方法不适合多条记录有相同关键码的应用程序。散列方法一般不适合范围检索。适合的是精确查找。有吗？那条记录是关键码值K呢？应用：主存的检索，磁盘的检索，组织存储在磁盘上的大型数据库。

适用情况，记录关键码值的范围很大，并且把记录存储在一个槽数目相对较少的表中。

散列函数：一般来说希望选择的散列函数能把记录以相同的概率分布到散列表的所有槽中。但是在一般情况下，根据关键码值的分布来选择散列函数。

一些常见的散列函数：取余、平方取中法，字符串散列函数，折叠方法——ASCII码累加起来 % M（散列表长）

开散列方法——单链方法

冲突解决方法之开散列方法。

《数据结构与算法分析》P212，最简单的形式是：把散列表中的每个槽定义为一个链表的表头，散列到一个槽的所有记录都放到这个槽的链表内。链表中的记录可以按照插入次序排列，按照关键码值次序排列，按照访问频率次序排列等等。

适用于主存中。

闭散列方法——开地址方法

把所有记录直接存储到散列表中。每条关键码值标记为$k_R$ ，记录R有一个基槽，就是$h(k_R)$ ，即由散列函数计算出来的槽。如果要插入一条记录R，另一条记录占据了R的基槽，就把R存储在表的其他槽内。

桶式散列。把散列表中的槽分成多个桶。先进入桶中的槽，再进入溢出槽里。散列函数把记录在各个桶之间平均分布，使得进入溢出桶的记录尽可能少。

适用于磁盘的散列表。可以把桶的大小设置为磁盘块的大小。

线性探查

当基槽被占用时，在散列表中找到一个空槽，冲突策略就到达这个组中的下一个槽。如果这个槽也被占用了，就找下一个空槽。探测序列由探测函数P生成。

template <typename Key, typename E>
void hashdict<Key,E>::hashInsert(const Key&k, const E&e){
  int home; // home position for k
  int pos = home = h(k); //Init proble sequence
  for (int i=1; EMPTYKEY!=(HT[pos]).key(); i++){
    pos = (home + p(k,i) % M); // probe
    Assert(k != (HT[pos]).key(), "Duplication not allowed!");
  }
  KVpair<Key,E> temp(k,e);
  HT[pos] = temp;
}

第i次对P调用，返回第i次要用到的偏移量。

探测函数：线性探测，避免聚集可P(k,i) = ci

好的探测序列是在回到基槽之前，把散列表的所有槽都走一遍。理想的探测函数应该在探查序列中随机的从未走过的槽中选择下一个位置，即探查序列应当是散列表位置的随机排列。如伪随机探查。$( h(K) + r_i ) mod M$, $r_i$ 是1到M-1之间的数的随机排列。