引入哈希

现有一个题目： 给定一个固定容量的数组array，往该数组中随机插入 1-10范围内的数字，并要求插入的数字不能重复。
思路一：边插入边判断是否有重复值
随机插入数据，要求数据不能重复，我们需要，一边插入，一边判断插入的数据是否存在于该数组中。
如果存在，则继续随机生成数据，然后再次判断。
可以专门给定一个查询值函数，一个插入函数。
这样的时间复杂度很高，因为查询值函数里有一个循环，插入函数还是一个循环。
代码实现：

  1.    public static void init_Ar(int[] ar){
  2.         int i = 0;
  3.         Random random = new Random();
  4.         while(i<ar.length){
  5.             int val = random.nextInt(10)+1;
  6.             if (findVal(ar,i,val)==-1){
  7.                 ar[i] = val;
  8.                 i++;
  9.             }
  10.         }
  11.     }
  12.     /**
  13.      * 查找值
  14.      * @param ar
  15.      * @param n：数组元素个数
  16.      * @return
  17.      */
  18.     private static int findVal(int[] ar,int n,int val){
  19.         int pos = -1;
  20.         for (int i = 0; i < n; i++) {
  21.             if (ar[i]==val){
  22.                 pos = i;
  23.                 break;
  24.             }
  25.         }
  26.         return pos;
  27.     }

思路二：通过查表的方法。
① 我们可以再给定一个数组记为table，这个table我们可以把它看做是表，其table的长度就是我array的长度。
② 我们不用给table赋值，其table中所有元素都为0，当我们要向array中插入元素val时，就想去table中的val位置查看，如果table[val] ==0，说明没有插入过该val，如果table[val]==1，说明已经差如果该val，则重新随机生成数据。
image.png
例：此时向i插入数据5时，会先在table表中查询table[5]的值是否为0，经查询后，发现不为0，所以不能插入，需要继续随机生成新的值。

代码实现：时间复杂度为O(n)、空间复杂度为S(n)

  1.     public static void init_Ar(int[] ar){
  2.         Random random = new Random();
  3.         int i = 0;
  4.         int []table = new int[ar.length];
  5.         while(i<ar.length){
  6.             int val =  random.nextInt(10)+1;
  7.             if (table[val] == 0){
  8.                 ar[i] = val;
  9.                 table[val] = 1;
  10.                 i++;
  11.             }
  12.         }
  13.     }
  1.   但是通过查表有一个问题，如果在array中插入的数据范围是 1~100000，此时要求array中的数据不重复。**此时，如果我们还想通过查表的方式，我们就得让table初始化的大小为100001，这样才能保证1~100000中的每个数据都在table表中，这样做的话，开辟的空间太大，有没有什么更好地办法呢？**

哈希

上面我们提出的问题，可以通过一张哈希表解决。

  1.    我们记一张哈希表为table。初始化时，key、value值都为0.<br />当向哈希表中 放入数据时，我们首先通过**哈希算法(该数据模哈希表长度得到的值)**<br />计算该数据存在于哈希表中的哪个位置。<br />如果哈希表中该位置上存在值，判断是否和要插入的数据相同，如果相同，则不让插入，如果不同，**则发生了哈希冲突。**<br />**此时，我们可以通过线性探测的方法，继续探测下一个位置上有没有数据，如果有，则继续找下一个位置，如果没有，则正常插入。**

示例：
哈希表：
image.png
现在，我们随机产生的数据为：11 24 37 50 2 3
哈希算法： (kx % maxsize)
在插入11时，我们会先通过哈希算法，计算在哈希表中的位置：
11 % 13 = 11,插入11的位置

继续插入24， 24 % 13 = 11，此时11位置上已经有数据了，我们如何通过线性探测的方式，让他往下探测呢？

这个时候，我们就需要改变一下哈希算法。
hashAgain = (hash(kx) + i) % maxsize
此时，插入24， 因为24是第二个插入的数据，所以i = 1。（i从0开始）计算出位置： (11 + 1) %13 = 12,位置12上没有数据，则正常插入。

再插入37， ((37%11) + 2 ) % 13 = 6，在位置6上插入，以此类推…
最终得哈希表：
image.png

哈希表的结构：
有一个key
有一个value
key代表要插入的数据
value可以理解成一个标识位。

  1. class HashTable{
  2.     class HashNode{
  3.         int key; // 表示要插入数据的值
  4.         int val; // 可以理解成一个标识符，当为1时，表示该位置上有数据了，当为0时，表示该位置上没有数据。
  6.         public HashNode(){
  7.             key = 0;
  8.             val = 0;
  9.         }
  10.     }
  11.     // 哈希表
  12.     HashNode[] table;// 哈希表
  13.     int maxsize; // 哈希表最大长度
  14.     public HashTable(int n){
  15.         maxsize = n;
  16.         table = new HashNode[maxsize];
  17.     }
  20.     public int hash(int kx){
  21.         return kx % maxsize;
  22.     }
  24.     // 线性探测需要用到
  25.     int inc(int i){return i;}
  27.     // 线性探测，如果存在哈希相同，但数据值不同，则线性探测。
  28.     public int hashAgain(int kx,int i){
  29.         return (hash(kx)+inc(i))%maxsize;
  30.     }
  32.     // 放入哈希表中。
  33.     public boolean put(int kx){
  34.         boolean res = false;
  35.         // 哈希表中该位置上已经存在值且该值不等于我们插入的数据，则我们需要进行线性探测
  36.         // 线性探测：即该位置上有值，就判断下一个位置是否有值，以此类推。
  37.         for (int i = 0; i < maxsize; i++) {
  38.             int pos = hashAgain(kx,i);
  39.             if (table[pos].val == 0){
  40.                 table[pos].key = kx;
  41.                 table[pos].val = 1;
  42.                 res = true;
  43.                 break;
  44.             }else if(table[pos].key==kx){
  45.                 break;
  46.             }
  47.         }
  50.         return res;
  51.     }
  52. }

此时array数组的插入函数应该为：

  1. public static void init_Ar(int[] ar){
  2.         Random random = new Random();
  3.         int i = 0;
  4.         int []table = new int[ar.length];
  5.         while(i<ar.length){
  6.             int val =  random.nextInt(10)+1;
  7.             HashTable ht = new HashTable(13);
  8.             if (ht.put(val)){
  9.                 ar[i] = val;
  10.                 i++;
  11.             }
  12.         }
  13.     }