#include<stdio.h>
#include<assert.h>
#define NIL -1
#define m 13
typedef int KeyType;
struct ElemType
{
  	KeyType key;
    void* ptr;	//value
};
typedef struct
{
    ElemType data[m];
    int cursize;
}HashTable;

void Init_HashTable(HashTable* pt)
{
    assert(pt != nullptr);
    pt->cursize = 0;
    for(int i=0;i<m;++i)
    {
        pt->data[i].key = NIL;
        pt->data[i].ptr = nullptr;
    }
}
int Hash(KeyType kx)
{
    return kx%m;
}
bool Insert_Item(HashTable* pt, ElemType item)
{
    assert(pt != nullptr);
    int index = Hash(item.key);
    pt->data[index] = item;
    pt->cursize += 1;
}
int main()
{
    HashTable ht;
    Init_HashTable(&ht);
    int ar[]={12,23,25,8,19,29};
    int n=sizeof(ar)/sizeof(ar[0]);
    for(int i=0;i<n;++i)
    {
        struct ElemType item = {ar[i],nullptr};
        bool tag = Insert_Item(&ht,item);
    }
}

int Inc(int i)
{
    return i;
}
int Hash_Inc(KeyType kx, int i)
{
    return (Hash(kx) + Inc(i))%m;
}
bool Insert_Item(HashTable* pt, ElemType item)
{
    assert(pt != nullptr);
    for(int i = 0;i<m;++i)
    {
        int index = Hash_Inc(item.key, i);
        if(pt->data[i].key == NIL)//随着Inc更迭，找到一个空位置
        {
            pt->data[index] = item;
            pt->cursize += 1;
            return true;
        }
    }
    return false;
}

int main()
{
    HashTable ht;
    Init_HashTable(&ht);
    int ar[]={12,15,28,23,25,38,36,49,14};
    int n=sizeof(ar)/sizeof(ar[0]);
    for(int i=0;i<n;++i)
    {
        struct ElemType item = {ar[i],nullptr};
        bool tag = Insert_Item(&ht,item);
    }
}

int Inc(int i)
{
    return i*i;
}

void* FindValue(HashTable* pt, KeyType kx)
{
    assert(pt != nullptr);
    for(int i = 0;i<m;++i)
    {
        int pos = Hash_Inc(kx,i);
        if(pt->data[pos].key==kx)
        {
            return pt->data[pos].ptr;
        }
        if(pt->data[pos].key==NIL)
        {
            return nullptr;
        }
    }
}

#include<stdio.h>
#include<assert.h>
#define m 13
typedef int KeyType;
typedef struct ElemType
{
    KeyType key;
    void* ptr;
}ElemType;
typedef struct HashNode
{
    ElemType data;
    struct HashNode* next;
}HashNode;
typedef struct HashTable
{
    HashNode* table[m];
    int cursize;
}HashTable;

int Hash(KeyType kx)
{
    return kx % m;
}
void Init_Hash(HashTable* pt)
{
    assert(pt!=nullptr);
    for(int i = 0;i<m;++i)
    {
        pt->table[i] = nullptr;
    }
    pt->cursize = 0;
}
void Insert_Item(HashTable* pt, ElemType item)//但是此函数没有解决存在相同key时的情况
{
    assert(pt!=nullptr);
    int index = Hash(item.key);
    HashNode* s = (HashNode*)malloc(sizeof(HashNode));
    if(nullptr == s) exit(1);
    s->data = item;
    s->next = pt->table[index];
    pt->table[index] = s;
    pt->cursize += 1;
}
int main()
{
    int ar[]={1,55,19,20,10,11,14,68,84,23,27,79};
    int n = sizeof(ar)/sizeof(ar[0]);
    HashTable ht;
    Init_Hash(&ht);
    for(int i = 0;i<n;++i)
    {
        ElemType elem = {ar[i],nullptr};
        Insert_Item(&ht,elem);
    }
}

void Init_Hash(HashTable* pt)
{
    assert(pt != nullptr);
    for(int i = 0;i<m;++i)
    {
        pt->table[i]=nullptr;
    }
    pt->cursize=0;
}

void Insert_Item(HashTable* pt, ElemType item)
{
    assert(pt != nullptr);
    int index = Hash(item.key);
    HashNode* pnode = (HashNode*)malloc(sizeof(*pnode));
    if (nullptr == pnode) exit(1);
    pnode->data = item;//讲外部elem封装到新建结点的数据域
    //以下两步为入表操作，采用头插法，时间复杂度为O(1)，不用判头结点是否为空
    pnode->next = pt->table[index];
    pt->table[index] = pnode;
    
    pt->cursize++;//现有大小+1
}

HashNode* FindNode(HashTable* pt, KeyType kx)
{
	int index = Hash(kx);
	HashNode* p = pt->data[index];
	while (p != nullptr && p->item.key != kx)
	{
		p = p->next;
	}
	return p;
}

//free掉所有节点，HashTable的指针数组数据全赋空
void ClearTable(HashTable* pt)
{
	for (int i = 0;i < m;++i)
	{
		HashNode* p = pt->data[i];
		HashNode* q = nullptr;
		while (p)
		{
			q = p->next;
			free(p);
			pt->cursize--;
			p = q;
		}
		pt->data[i] = nullptr;
	}
}

void ClearHash(HashTable* pt)
{
    for(int i = 0;i<m;++i)
    {
        while(pt->data[i]!=nullptr)
        {
            HashNode* q = pt->data[i];
            pt->data[i]=q->next;
            free(q);
        }
    }
    pt->cursize=0;
}

//删除某一节点，需用到两个指针变量，一前一后。
void RemoveNode(HashTable* pt, KeyType kx)
{

	int index = Hash(kx);
	HashNode* p = pt->data[index];
	if (p == nullptr) exit(1);//不存在要删除的key的对应节点，因为Table数组此下标的值既然为空则肯定不会有key值相应的节点存在
	HashNode* q = p->next;
	//若删除的节点为头结点，则特殊处理
	if (p->item.key == kx)
	{
		pt->data[index] = q;
		free(p);
	}
	else//
	{
		while (q != nullptr && q->item.key != kx)
		{
			p = p->next;
			q = q->next;
		}
		if (q == nullptr) exit(1);//不存在要删除的key的对应节点，因为遍历这一条链后不存在相同的key值对应的节点。
		else//q->item.key == kx
		{
			p->next = q->next;
			free(q);
		}
	}
	pt->cursize--;
	return;
}

//Remove节点更老套的写法：
bool Remove(HashTable* pt,KeyType kx)
{
    assert(pt!=nullptr);
    int index=Hash(kx);
    HashNode* pr=nullptr;//前驱指针
    HashNode* p=pt->table[index];
    while(p!=nullptr)
    {
        if(p->item.key==kx)
        {
            if(pr!=nullptr)
            {
                pr->next=p->next;
            }
            else
            {
                pt->table[index]=p->next;
            }
            free(p);
            pt->total-=1;
            return true;
        }
        pr=p;
        p=p->next;
    }
    return false;
}

int* My_NonRepeating_RandArr(int* ar, int n)
{
    assert(ar != nullptr);
    int br[101];
    for (int i = 0;i < n + 1;++i)
    {
        br[i]=0;
    }
    int temp;
    srand(time(NULL));
    int i = 0;
    do
    {
        temp = rand() % 100 + 1;
        if (br[temp] != 1)
        {
            br[temp] = 1;
            ar[i] = temp;
            ++i;
        }
    } while (i<n);
    return ar;
}

#include<stdio.h>
#include<assert.h>
#define m 100
typedef int KeyType;
typedef struct ElemType
{
    KeyType key;
    void* ptr;
}ElemType;
typedef struct HashNode
{
    ElemType data;
    struct HashNode* next;
}HashNode;
typedef struct HashTable
{
    HashNode* table[m];
    int cursize;
}HashTable;
void Init_Hash(HashTable* pt)
{
    assert(pt != nullptr);
    for(int i = 0;i<m;++i)
    {
        pt->table[i]=nullptr;
    }
    pt->cursize=0;
}
void Insert_Item(HashTable* pt, ElemType item)
{
    assert(pt != nullptr);
    int index = Hash(item.key);
    HashNode* pnode = (HashNode*)malloc(sizeof(*pnode));
    if (nullptr == pnode) exit(1);
    pnode->data = item;//讲外部elem封装到新建结点的数据域
    //以下两步为入表操作，采用头插法，时间复杂度为O(1)，不用判头结点是否为空
    pnode->next = pt->table[index];
    pt->table[index] = pnode;
    
    pt->cursize++;//现有大小+1
}
int Hash(KeyType kx)
{
    return kx%m;
}
HashNode* FindValue(HashTable* pt, KeyType kx)
{
    int index = Hash(kx);
    HashNode* p = pt->table[index];
    while(p != nullptr && p->data.key != kx)
    {
        p=p->next;
    }
    return p;
}
int* My_NonRepeating_Hash(int* ar, int n)
{
    assert(ar != nullptr);
    HashTable ht;
    Init_Hash(&ht);
    int temp;
    srand(time(NULL));
    int i = 0;
    do
    {
        temp = rand()* rand() % 1000000 + 1;
        if (FindValue(&ht, temp) == nullptr || *(int*)(FindValue(&ht, temp)->data.ptr) != 1)
        {
            ElemType item = { temp,new int(1) };
            Insert_Item(&ht, item);
            ar[i] = temp;
            ++i;
        }
    } while (i < n);
    return ar;
}
int main()
{
    
}

#include<assert.h>
#define m 13
#define INC	2
typedef int KeyType;
typedef struct
{
    KeyType key;
    void* ptr;
}ElemType;
typedef struct HashNode
{
    ElemType data;
    struct HashNode* next;
}HashNode;
typedef struct HashTable
{
    HashNode** table;
    int capacity;
    int total;
}HashTable;
int Hash(HashTable* pt, KeyType kx)
{
    //return kx % m; //原始不考虑增容的情况下默认%m
    return kx % pt->capacity;
}
void Init_Hash(HashTable* pt)
{
    assert(pt!=nullptr);
    pt->table = (HashNode**)malloc(sizeof(HashNode*)*m);
    if(pt->table == nullptr)exit(EXIT_FAILURE);
    pt->capacity = m;
    for(int i = 0;i<pt->capacity;++i)
    {
        pt->table[i] = nullptr;
    }
    pt->total = 0;
}
HashNode* FindNode(HashTable* pt, KeyType kx)
{
    int index = Hash(pt,kx);
    HashNode* p = pt->table[index];
    while(p != nullptr && p->data.key != kx)
    {
        p=p->next;
    }
    return p;
}
bool Inc(HashTable* pt)//对哈希表的增容操作
{
    int incsize = pt->capacity * INC;//INC为增容系数，默认为2，incsize表示增容后的新大小，为此前哈希表容量的2倍。
    HashNode** newtable = (HashNode**)malloc(sizeof(HashNode*)*incsize);
    if(newtable == nullptr)return false;
    for(int i = 0;i<incsize;++i)
    {
        newtable[i] = nullptr;
    }
    pt->captacity = incsize;
    //以上，开辟新的哈希表完毕，下面要把旧表复制到新表
    int oldsize = pt->capacity;
    for(int i = 0;i<oldsize;++i)
    {
        if(pt->table[i]!=nullptr)
        {
            
        }
    }
}
bool Insert_Item(HashTable* pt, ElemType item)
{
    assert(pt!=nullptr);
    HashNode* p = FindNode(pt,item.key);
    if(p!=nullptr)return false;//哈希表中已存在相同key值的节点
    if(pt->total > pt->capacity && !Inc(pt))//需要增容但没有增容成功
    {
        return false;
    }
    int index 
}

typedef struct dictht
{
    dictEntry** table;//哈希表数组
    unsigned long size;//哈希表大小
    unsigned long sizemark;//哈希表大小掩码，用于计算索引值。总是等于size-1
    unsigned long used;//表中已有节点的数量
}dictht;

typedef struct dictEntry
{
    void* key;
    union
    {
        void* val;
        uint64_tu64;
        int64_ts64;
    }v;
    struct dictEntry* next;
}dictEntry;

typedef struct dictType 
{
    // 计算哈希值的函数
    unsigned int (*hashFunction)(const void *key);
    // 复制键的函数
    void *(*keyDup)(void *privdata, const void *key);
    // 复制值的函数
    void *(*valDup)(void *privdata, const void *obj);
    // 对比键的函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    // 销毁键的函数
    void (*keyDestructor)(void *privdata, void *key);
    // 销毁值的函数
    void (*valDestructor)(void *privdata, void *obj);
} dictType;
typedef struct dict
{
    dictType* type;//结构体指针，用于存放特定类型的操作函数
    void* privdata;//私有数据
    dictht ht[2];//内部定义了两个哈希表
    int rehashidx;//当没有在rehash时值为-1
}dict;

/*
 * 返回以毫秒为单位的 UNIX 时间戳
 *
 * T = O(1)
 */
long long timeInMilliseconds(void) 
{
    struct timeval tv;

    gettimeofday(&tv,NULL);
    return (((long long)tv.tv_sec)*1000)+(tv.tv_usec/1000);
}
/* Rehash for an amount of time between ms milliseconds and ms+1 milliseconds */
/*
 * 在给定毫秒数内，以 100 步为单位，对字典进行 rehash 。
 *
 * T = O(N)
 */
int dictRehashMilliseconds(dict *d, int ms) 
{
    // 记录开始时间
    long long start = timeInMilliseconds();
    int rehashes = 0;

    while(dictRehash(d,100)) {
        rehashes += 100;
        // 如果时间已过，跳出
        if (timeInMilliseconds()-start > ms) break;
    }

    return rehashes;
}