class HashTable:
    def __init__(self, size):
        self.elem = [None for i in range(size)]  # 使用list数据结构作为哈希表元素保存方法
        self.count = size  # 最大表长
 
    def hash(self, key):
        return key % self.count  # 散列函数采用除留余数法
 
    def insert_hash(self, key, value):
        """插入关键字到哈希表内"""
        address = self.hash(key)  # 求散列地址
        while self.elem[address]:  # 当前位置已经有数据了，发生冲突。
            address = (address + 1) % self.count  # 线性探测下一地址是否可用
        self.elem[address] = value  # 没有冲突则直接保存。
 
    def search_hash(self, key):
        """查找关键字，返回布尔值"""
        star = address = self.hash(key)
        while self.elem[address] != key:
            address = (address + 1) % self.count
            if not self.elem[address] or address == star:  # 说明没找到或者循环到了开始的位置
                return False
        return True
if __name__ =="__main__":     
     hash1=HashTable(7)
     hash1.insert_hash(1,11)
     hash1.insert_hash(2,12)
     hash1.insert_hash(3,13)
     hash1.insert_hash(4,14)
     print(hash1.search_hash(14))
 
 

 
 
我们都知道，当我们要在一个集合中查找数据时，如果这个集合是顺序表且我们能确定要找的数据在顺序表中的位置的话，我们就能通过下标直接找到元素，这无非是我们要追求的最高效的查找策略！但是现实总是那么骨感，在大多数情况下，要在茫茫数据海洋中找某些关键信息，是不可能直接找到的。因为我们并不知道我们要找的数据与其所在位置之间是否存在某种关联。
 
 
 
 
所以我们在存储数据时，建立如同顺序表形式的可以按照下标进行查找的存储集合，然后我们可以认为建立要存的关键信息和其在集合中的下标之间的关系，这样我们在找想找的信息时，就可以确定信息在集合中的下标了，这样就可实现较为高效的查找了。而我们所说的这个集合就称为哈希表，建立的下标与信息的关系可以通过哈希函数(自定义合理的函数)来实现。
 
 
 
 
哈希表在查找，加密等很多方面都有广泛用途。
 今天我用拉链法建立了简单的哈希表其结构如图所示：
 
 
 
源码
 
#include <iostream>
#include<array>
#include<memory>
#include<string>
#include<vector>
using namespace std;

class data{
public :
    string name;
    int age;
    data(){
    }
    ~data(){}
};
class info:public data{

public :
    vector<data>ls;
    info(){
    }
    ~info(){}
    static void init(array<shared_ptr<info>,27>&ss);
    static void input(array<shared_ptr<info>,27>&ss);
    static int getLoc(char a);;
    static void search(array<shared_ptr<info>,27>&ss);
};

void info::search(array<shared_ptr<info>,27>&ss){

    string name ;
    cin>>name ;
    int index = getLoc(name[0]);
    if(index==-1){
        cout<<"No the name"<<endl;
    }
    int i =0 ;
    int flag =1;
    for(i=0;i<(int)ss[index]->ls.size();i++){
        if(ss[index]->ls[i].name==name){
            flag =0;
            cout<<"The info of the person:"<<endl;
            cout<<" \nAge:"<<ss[index]->ls[i].age<<"      "<<"Name:"<<ss[index]->ls[i].name<<endl;
            break;
        }
    }
    if(flag ==1){
        cout<<"No the info"<<endl;
    }
}
int info::getLoc(char a){
    
            if(a>='A'&&a<='Z'){
                return a-65;
            }
             else if(a>='a'&&a<='z'){
                return a-97;
            }
            else{
                return -1;
        }
}
void info::input(array<shared_ptr<info>,27>&ss){
    string name ;
    cout<<"请输入姓名(由英文字符组成)和年龄 -1 to return..."<<endl;
    while(1){
        data dd;
        cin>>dd.name ;
        if(dd.name=="-1"){
                break;
            }
        cin>>dd.age;
        //差试用一下lamda表达式
        auto key= [dd](){
            if(dd.name[0]>='A'&&dd.name[0]<='Z'){
                return dd.name[0]-65;
            }
             else if(dd.name[0]>='a'&&dd.name[0]<='z'){
                return dd.name[0]-97;
            }
            else if(dd.name[0]==' '){
                return 0;
            }
            else{
                return -1;
        }
        };
        int index= key();
        if(index==-1){
            cout<<"The name is error!"<<endl;
            continue ;
        }
        ss[index]->ls.push_back(dd);
    }
}
void info::init(array<shared_ptr<info>,27>&ss){  
    int i;
    for(i=0;i<27;i++){
        shared_ptr<info>p(new info());
        ss[i]=p;
    }
}
int main()
{
    array<shared_ptr<info>,27>ss;
    info::init(ss); 
    info::input(ss);
    info::search(ss);
    return 0;
}
 
 
 
这个程序刚开始创建了info类的指针数组，info类继承了data类，info类里面有个vector容器主要存data类数据信息的。举个例子吧，要是name首字母是A，根据key = (大写字母-65)，则该data类所有信息就存在以下标为key的数组中的vector容器中，即ss[key].ls.push_back(含相应name关键字的对象)，后面同样的实现方法。在找时只需根据name首字母将要搜索的范围缩小，然后只能一个个遍历vector容器了。程序总的逻辑
 很简单，使用拉链法，哈希冲突也比较容易解决。
 

哈希表创建
 
哈希表（Hash Table，也叫散列表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做哈希函数，存放记录的数组称做哈希表。哈希表相关定义如下：
 
typedef enum{
    HASH_OK,
    HASH_ERROR,
    HASH_ADDED,
    HASH_REPLACED_VALUE,
    HASH_ALREADY_ADDED,
    HASH_DELETED,
    HASH_NOT_FOUND,
} HASH_RESULT;

typedef struct __HashEntry HashEntry;
struct __HashEntry{
    union{
        char  *str_value;
        double dbl_value;
        int       int_value;
    } key;
    union{
        char  *str_value;
        double dbl_value;
        int       int_value;
        long   long_value;
        void  *ptr_value;
    } value;
    HashEntry *next;
};

struct __HashTable{
    HashEntry **bucket;        
    int size;
    HASH_RESULT last_error;
};
typedef struct __HashTable HashTable;

// 创建大小为hash_size的哈希表，创建成功后返回HashTable类型的指针，否则返回NULL。
HashTable *create_hash(int hash_size);
哈希表相关说明：

HASH_RESULT 类型为相关函数的返回类型
HashEntry 为哈希表所保存元素（即键值对 《key, value》）类型
HashTable 为哈希表，其中 bucket 指向大小为size的、元素类型为 HashEntry*的指针数组
哈希表采用链地址法处理冲突
请实现 create_hash 函数，创建指定大小的哈希表。
 
答案
 
#include “hash.h”
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 
HashTable* create_hash(int size)
 {
 HashTable* H;
 H = (HashTable*)malloc(1 * sizeof(HashTable));
 if (H == NULL)
 return NULL;
 H->bucket = (HashEntry**)malloc(size * sizeof(HashEntry*));
 if (H->bucket == NULL) {
 free(H);
 return NULL;
 }
 memset(H->bucket, 0, size * sizeof(HashEntry*));
 H->size = size;
 H->last_error = HASH_OK;
 return H;
 }

2018.09.06
 
代码块
 
哈希表的拉链法实现： 
  
 定义哈希表的定义链结点
 
#define HASHSIZE 15
typedef unsigned int uint;
typedef struct Node{
    const char* key;
    const char* value;
    Node *next;
}Node;

class HashTable{
private:
    Node* node[HASHSIZE];
public:
    HashTable();
    uint hash(const char* key);
    Node* lookup(const char* key);
    bool install(const char* key,const char* value);
    const char* get(const char* key);
    void display();
};

HashTable::HashTable(){
    for (int i = 0; i < HASHSIZE; ++i)
    {
        node[i] = NULL;
    }
}
 
定义哈希表的Hash算法：time33算法（没找到什么理论可以说明这种算法的合理性，据说只是通过测试和实践发现这个算法是比较好的）
 
uint HashTable::hash(const char* key){
    uint hash=0;
    for (; *key; ++key)
    {
        hash=hash*33+*key;
    }
    return hash%HASHSIZE;
}
 
哈希表的查找
 
Node* HashTable::lookup(const char* key){
    Node *np;
    uint index;
    index = hash(key);
    for(np=node[index];np;np=np->next){
        if(!strcmp(key,np->key))
            return np;
    }
    return NULL;
}
 
插入一个新的结点，首先是查看该key值的结点是否存在，如果存在则更改value值就好，如果不存在，则插入新结点。
 
bool HashTable::install(const char* key,const char* value){
    uint index;
    Node *np;
    if(!(np=lookup(key))){
        index = hash(key);
        np = (Node*)malloc(sizeof(Node));
        if(!np) return false;
        np->key=key;
        np->next = node[index];
        node[index] = np;
    }
    np->value=value;
    return true;
}
 
链地址法可以解决哈希冲突