資料結構與算法實踐系列文章（八）散列

散列

散列

目标 ：為了更快的查找 —O(1),拿空間換時間， 計算空間位置更快

定義

“鍵 -值 對” （key- value pair）的集合

兩個關鍵的問題

• 散列函數 什麼是好的散列函數
• 解決沖突 如何進行解決沖突

解決沖突方式

• 開放定址
• 分離鍊
• 其他（公共溢出）

開放定址

h(x) = x mod 11

x={12,2,17,28,6,23} h(x) = {1,2,6,6,1}

這樣以來就有沖突了，這個當沖突時則可以将資料進行往後的坐标點放入 可進行 線性探測，平方探測。。。

分離鍊

h(x) = x mod 11

x={12,2,17,28,6,23} h(x) = {1,2,6,6,1}

是在這個結點做個連結清單結點 。單連結清單的插入删除

C實作

// 開放定址法，删除時時不能真正的删，隻能邏輯的删除，讓其标記
#include <stdio.h>
#include <stdio.h>
// 标記的狀态
enum GridStatus{Active,Removed,Empty};
typedef enum GridStatus Status;
struct HashTable{
    int *key; // key
    Status *status; // 标記的狀體
    int size; // 表裡的大小
    int remains; // 表中剩餘的大小
};
typedef struct HashTable *HT;
HT initHashTable(int size){
    HT h;
    h= (HT) malloc(sizeof(struct HashTable));
    if(!h) return NULL;
    h->size = h->remains =size;
    h->key = (int *)malloc(sizeof(Status)* size);
    if(!h->status){ free(h->key);free(h); return NUll;}
    for(int i=0;i<size;i++){
        h->status[i]=Empty;
    }
    return h;
}
// hash函數
int hash(int x,int p){
    return x%p;
}
int isFull(const HT h){
    return h->remains == 0;
}
// 插入
int insertX(int x, HT h){
    if(isFull(h)) return 0;
    int pos=hash(x,h->size);
    while(h->status[pos] == Active){
        pos = (pos+1) % h -> size;
    }
    h->key[pos] = x;
    h->status[pos] =Active;
    h->remains--;
    return 1;
}
// 查找
int findX(int x,HT h){
  int pos,index;
  index=pos= hash(x,h->size);
  while(h-status[pos]!=Empty){
      if(h->key[pos] == x && h-status[pos] == Active) return pos;
      pos= (pos+1)% h->size; // 循環一圈
      if(pos == index) break;
      return -1;
  }
}
//remove
int removeX(int x, HT h){
    int pos = findX(x,h);
    if(pos==-1) return 0;
    // 隻做标記，不修改其中的值，這是絕大部分就是這樣的。
    h->status[pos] = Empty; 
}
void printHT(const HT h){
    for(int i=0;i<h-size;i++){
        printf("%4d",i){
    }
    putchar('\n');
    for(int i=0;i<h-size;i++){
        if(h->status[i] == Active) printf("%4d",h->key[i]);
        else if(h->status[i]==Removed) printf("   X");
        else printf("   -");
    }
    putchar('\n');
}
int main(){
    HT h=initHashTable(11);
    insertX(5,h);
    return 0;
}
           

C++

#include <iostream>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
using namespace std;
int main() {
    unordered_set<int> s;
    unordered_map<int, int> m;
    m[101] =33;
    m[-10] = 2233;
    m.inser(pair<int,int>(22,33));
    return 0;
}
           

Java

Map-->HashMap; 鍵值對映射
Set--->HashSet;

           

JAVA中的hashmap是在jdk1.8以前時采用的時數組+連結清單，jdk1.8以後采用的是數組+連結清單+紅黑樹，當元素的個數在8時将連結清單轉為紅黑樹，是以hashmap的元素的個數在8左右時會将消耗性能。hashMap的初始值元素的個數為16，hashMap的自增因子為0.75，當元素個數為32的時候初始容量為 32/0.75= 。

Python

d = dict() # 字典
d[100] =50