hash链表_双向hash链表 - CSDN
  • 线性表(3)——哈希链表

    千次阅读 2019-03-26 23:24:56
    C++实现: Key_Value_Pair.h #pragma once #ifndef Key_Value_Pair_H #define Key_Value_Pair_H template <typename Key, typename Value> class Key_Value_Pair { public: ... typedef ...

    C++实现:

    Key_Value_Pair.h

    #pragma once
    #ifndef Key_Value_Pair_H
    #define Key_Value_Pair_H
    template <typename Key, typename Value>
    class Key_Value_Pair
    {
    public:
    	typedef Key  Key_Type;
    	typedef Key& Key_Reference;
    	typedef Key* Key_Pointer;
    	typedef const Key& Const_Key_Reference;
    
    	typedef Value  Value_Type;
    	typedef Value& Value_Reference;
    	typedef Value* Value_Pointer;
    	typedef const Value& Const_Value_Reference;
    public:
    	Key_Type key;
    	Value_Type value;
    
    public:
    	Key_Value_Pair()
    	{}
    	//有参构造
    	Key_Value_Pair(Key_Type m_key, Value_Type m_value)
    		:key(m_key), value(m_value)
    	{}
    	//拷贝构造
    	Key_Value_Pair(const Key_Value_Pair& m_KV_Pair)
    		:key(m_KV_Pair.key), value(m_KV_Pair.value)
    	{}
    	//重载赋值运算符
    	void operator= (const Key_Value_Pair& m_KV_Pair)
    	{
    		key = m_KV_Pair.key;
    		value = m_KV_Pair.value;
    	}
    
    };
    #endif // !Key_Value_Pair_H

    Single_Link_List_Node.h

    #pragma once
    #ifndef SINGLE_LINK_LIST_NODE
    #define SINGLE_LINK_LIST_NODE
    
    template <typename T>
    class Single_Link_List_Node
    {
    public:
    	typedef T  Value_Type;
    	typedef T* Value_Pointer;
    	typedef T& Value_Reference;
    	typedef const T& Const_Value_Reference;
    	typedef Single_Link_List_Node  Node;
    	typedef Single_Link_List_Node*  Node_Pointer;
    	typedef const Single_Link_List_Node&  Const_Node_Reference;
    	typedef Single_Link_List_Node* Next_Pointer;
    	typedef Node* Node_Pool;
    
    private:
    	static  Node_Pool node_Pool;  //声明为static变量,让所有对象共享
    public:
    	Value_Type value;   //结点存储的值
    	Next_Pointer next;  //结点保存的指向下一个结点的指针
    
    	//结点构造函数,创建结点,对应C语言实现的create函数
    	Single_Link_List_Node(Const_Value_Reference m_value, Next_Pointer m_next = nullptr)
    		:value(m_value), next(m_next)
    	{
    	}
    	//默认构造函数
    	//为头指针,尾指针,当前指针的定义提供不用没有值的构造方法
    	Single_Link_List_Node(Next_Pointer m_next = nullptr)
    	{}
    
    	//重载new运算符
    	void* operator new(size_t)
    	{
    		//内存池中没有申请到结点内存时,调用全局的new申请内存直接返回
    		if (node_Pool == nullptr)
    			return ::new Node;
    		//内存池中有结点时
    		Node_Pointer temp = node_Pool;
    		//从内存池中申请后,内存池中结点减少,即内存池首地址的指向下一个结点区域
    		node_Pool = node_Pool->next;
    		return temp;
    	}
    
    	//重载delete运算符
    	void operator delete(void* free_node)
    	{
    		//释放结点内存直接将结点释放到内存池中
    
    		//每释放一个都插入到内存池的头部
    		//让释放的结点指向内存池首地址
    		((Node_Pointer)free_node)->next = node_Pool;
    		//让内存池的首地址指向释放的结点
    		node_Pool = (Node_Pointer)free_node;
    	}
    
    	bool operator==(Const_Node_Reference node)
    	{
    		if (value == node.value && next == node.next)
    			return true;
    	}
    };
    //类的静态变量的初始化
    template <typename T>
    Single_Link_List_Node<T>* Single_Link_List_Node<T>::node_Pool = nullptr;
    #endif 

    Single_Link_List.h

    #pragma once
    #include "Single_Link_List_Node.h"
    #include <string>
    #include <iostream>
    
    template <typename T>
    class Single_Link_List
    {
    public:
    	typedef Single_Link_List_Node<T>  Node;
    	typedef Single_Link_List_Node<T>* Node_Pointer;
    	typedef Single_Link_List_Node<T>* Head_Type;
    	typedef Single_Link_List_Node<T>* Tail_Type;
    	typedef Single_Link_List_Node<T>* Current_Type;
    	typedef T Value_Type;
    	typedef const T&  Const_Value_Reference;
    private:
    	Head_Type head;
    	Tail_Type tail;
    	Current_Type curr;
    	int list_Length;
    
    	//初始化的函数,只用于此类,不提供对外接口
    	void init()
    	{
    		head = tail = curr = new Node;
    		list_Length = 0;
    	}
    
    	void removeAll()
    	{
    		while (head != nullptr)
    		{
    			curr = head;
    			head = head->next;
    			delete curr;
    		}
    	}
    
    	//满足某种异常条件,抛出异常,打印错误信息
    	void judge_OutOfRange(bool condition, const std::string& printInfo)
    	{
    		try
    		{
    			if (condition)
    			{
    				throw condition;
    			}
    		}
    		catch (bool)
    		{
    			std::cerr << printInfo << std::endl;   //为什么不要在.h文件中使用using namespace std?
    			exit(1);
    		}
    	}
    public:
    	Single_Link_List()
    	{
    		init();
    	}
    	~Single_Link_List()     //这里析构函数其实还是虚函数,因为它的父类是
    	{
    		removeAll();
    	}
    
    	void clear() 
    	{
    		removeAll();
    		init();
    	}
    
    
    	//Single_Link_List(const Single_Link_List& list)
    	//{
    	//	init();
    	//}
    	//默认删除和插入操作都是对当前结点的下一个结点操作,这样写方便操作
    	void insert(Const_Value_Reference value) 
    	{
    		Node* temp = curr->next;
    		curr->next = new Node;			//使用operator new分配内存
    		::new(curr->next)Node(value, temp);
    		if (curr == tail)				//记得判断尾节点的特殊情况
    			tail = curr->next;
    		list_Length++;
    	}
    
    	void append(Const_Value_Reference value) 
    	{
    		tail->next = new Node(value, nullptr);
    		tail = tail->next;
    		list_Length++;
    	}
    
    	Value_Type remove() 
    	{
    		//判断链表是否为空
    		judge_OutOfRange((curr->next == nullptr), "Link_List is none!");
    
    		Value_Type remove_value = curr->next->value;
    
    		//移除一个结点:让当前结点的下一个结点的指针,指向下一个结点的下一个结点,同时释放当前下一个结点
    		Node* temp = curr->next;
    		if (tail == curr->next)
    			tail = curr;
    		curr->next = curr->next->next;
    		delete  temp;
    		list_Length--;
    
    		return remove_value;
    	}
    
    	void prev() 
    	{
    		if (curr == head)
    			return;
    		Node* temp = head;
    		while (temp->next != curr)
    			temp = temp->next;
    		curr = temp;
    	}
    
    	void next() 
    	{
    		if (curr != tail)
    			curr = curr->next;
    	}
    
    	int length() const
    	{
    		return list_Length;
    	}
    
    	Const_Value_Reference getValue()  
    	{
    		//判断链表是否为空
    		judge_OutOfRange((curr->next == nullptr), "Link_List is none!");
    
    		return curr->next->value;
    	}
    
    	int currPos()const 
    	{
    		Node* temp = head;
    		int i;
    		for (i = 0; temp != curr; i++)
    		{
    			temp = temp->next;
    		}
    		return i;
    	}
    
    	void moveToPosition(int position) 
    	{
    		if(list_Length!=0)
    			judge_OutOfRange((position < 0 || position >= list_Length), "Position is out of range!");
    		curr = head;
    		for (int i = 0; i < position; i++)
    			curr = curr->next;
    	}
    
    
    
    	Current_Type getCurr()
    	{
    		return curr->next;
    	}
    };

    Hash_Link_Table.h

    #pragma once           
    #ifndef HASH_TABLE_H
    #define HASH_TABLE_H
    #include <iostream>
    #include "Single_Link_List_Node.h"
    #include "Single_Link_List.h"
    #include "Key_Value_Pair.h"
    
    #define DEFAULT_SIZE 10
    template<typename Value>
    class HashTable
    {
    public:
    	typedef Value* Value_Pointer;
    	typedef Value& Value_Reference;
    	typedef const Value& Const_Value_Reference;
    
    	typedef int Key;
    	typedef int* Key_Pointer;
    	typedef int& Key_Reference;
    	typedef const int& Const_Key_Reference;
    
    	typedef Single_Link_List_Node<Key_Value_Pair<Key, Value>>* Return_Node_Pointer;
    	typedef Single_Link_List_Node<Key_Value_Pair<Key, Value>>* Next_Pointer;
    	typedef Single_Link_List<Key_Value_Pair<Key, Value>> List;
    	typedef Single_Link_List_Node<Key_Value_Pair<Key, Value>> Node;
    	typedef Single_Link_List_Node<Key_Value_Pair<Key, Value>>* Node_Pointer;
    	typedef Single_Link_List_Node<Key_Value_Pair<Key, Value>>* Curr_Node;
    	typedef Key_Value_Pair<Key, Value> Key_Value_Pair;
    private:
    	int array_Size;     //数组的长度
    	List* list_Array;   //链表数组
    	int size;    //元素个数
    
    	Curr_Node curr;
    
    	//哈希函数:根据key值来计算索引,定位Hash桶的位置
    	int hash_function(int key)
    	{
    		return key % array_Size;
    	}
    public:
    	//创建哈希链表
    	HashTable(int size=DEFAULT_SIZE)
    	{
    		array_Size = size;
    		list_Array = new List[array_Size];
    
    	}
    
    	//插入
    	void insert(Key key,Value value)
    	{
    		int isExist = find(key);
    
    		if (isExist==0)
    		{
    			//新建一个结点
    			List *temp = &list_Array[hash_function(key)];
    			Key_Value_Pair* temp_Pair = new Key_Value_Pair(key, value);
    			temp->insert(*temp_Pair);
    			size++;
    		}
    		else
    		{
    			std::cout << "待插入的值已经存在于哈希表中";
    		}
    	}
    
    	//删除
    	Value remove(Key key)
    	{
    		int isExist = find(key);
    
    		if (isExist==1)
    		{
    			
    			List *temp_List = &list_Array[hash_function(key)];
    			Key_Value_Pair temp_Pair=temp_List->remove();
    			size--;
    			return temp_Pair.value;
    		}
    		else
    		{
    			std::cout << "待删除的结点不在哈希表中" << std::endl;
    		}
    	}
    
    	//查找
    	int find(Key key)
    	{
    		List *temp_List = &list_Array[hash_function(key)];
    		//找了很久的Bug:
    
    		//List temp_List = list_Array[hash_function(key)];
    		//在初始化的时候我从内存池中申请的空间给list_Array[hash_function(key)]的,
    		//结果这里局部变量temp_List在函数执行完的时候,调用了析构函数,把它释放了
    		//分析原因:当我没有写拷贝构造函数时,这里进行了浅拷贝,
    		          //List的head,tail,curr只是进行了赋值,仍然和原对象指向相同的地址
    		//解决方法:将局部对象的定义该成指针,就不会在析构的时候调用析构函数
    
    		temp_List->moveToPosition(0);
    		for (int i = 0; i < temp_List->length(); i++)
    		{
    			Key_Value_Pair temp_Pair =temp_List->getValue();
    			if (temp_Pair.key == key)
    			{
    				curr = temp_List->getCurr();
    				return 1;
    			}	
    		}
    		return 0;
    	}
    
    	Value getValue()
    	{
    		return (curr->value).value;
    	}
    
    	//遍历打印
    	void print()
    	{
    		for (int i = 0; i < array_Size; i++)
    		{
    			for (int j = 0; j < list_Array[i].length(); j++)
    			{
    				list_Array[i].moveToPosition(j);
    				std::cout << list_Array[i].getValue().value << std::endl;
    			}
    		}
    	}
    
    	int length()
    	{
    		return size;
    	}
    };
    #endif

    main.cpp

    #include "Hash_Link_Table.h"
    #include <iostream>
    #include<string>
    using namespace std;
    
    typedef int Postion;
    int main()
    {
    	string names[4]= { "TuCheng","Lily","YanWanli","CaiLinjin" };
    
    	
    	HashTable<string> hashTable;
    
    	cout << "测试insert,find,getValue" << endl;
    	hashTable.insert(0,names[0]);
    	hashTable.insert(1,names[1]);
    	hashTable.insert(2,names[2]);
    	hashTable.insert(3,names[3]);
    
    	for (int i = 0; i < 6; i++)
    	{
    		int temp= hashTable.find(i);
    		if (temp==1)
    			cout << hashTable.getValue() << endl;
    		else
    			cout << "你查找的值不存在!" << endl;
    	}
    
    	cout << "\n测试length" << endl;
    	cout << "哈希表中元素的个数为:" << endl;
    	cout << hashTable.length() << endl;
    
    	cout << "\n遍历哈希表打印每一个元素" << endl;
    	hashTable.print();
    
    	cout << "\n测试remove" << endl;
    	hashTable.remove(2);
    	cout << "\n哈希表中元素的个数为:" << endl;
    	cout << hashTable.length() << endl;
    	cout << "\n遍历哈希表打印每一个元素" << endl;
    	hashTable.print();
    }
    

    运行结果:

    展开全文
  • hash链表

    千次阅读 2014-03-23 19:30:17
    hash链表概述 hash链表是hash表和链表的结合,使用比较方便。 hash链表实现 本文的hash链表实现:hash头部用单链表、其他的hash节点用双向链表。实现主要取自Linux内核实现,本文做了移植。本文代码可从...

    hash链表概述

    hash链表是hash表和链表的结合,使用比较方便。

    hash链表实现

    本文的hash链表实现:hash头部用单链表、其他的hash节点用双向链表。实现主要取自Linux内核实现,本文做了移植。本文代码可从http://download.csdn.net/detail/it_pcode/6632905下载。

    hash实现

    #ifndef HLIST_H_
    #define HLIST_H_
    
    #include <stdlib.h>
    #include <stddef.h>
    #include <stdio.h>
    #include <time.h>
    #include <string.h>
    
    /*通过父结构体type中的成员member的已知地址ptr,来寻找当前ptr地址所属的父结构体type的地址*/
    #define container_of(ptr, type, member) ({ \
    const typeof( ((type *)0)->member ) *__mptr = (ptr); \
    (type *)( (char *)__mptr - offsetof(type,member) );})
    
    /*内核预加载内容到RAM,在此不做实现*/
    #define prefetch(x) (x)
    
    /*
     * Double linked lists with a single pointer list head.
     * Mostly useful for hash tables where the two pointer list head is
     * too wasteful.
     * You lose the ability to access the tail in O(1).
     */
    
    struct hlist_head {
    	struct hlist_node *first;
    };
    
    struct hlist_node {
    	struct hlist_node *next, **pprev;
    };
    
    #define HLIST_HEAD_INIT { .first = NULL }
    #define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
    #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
    static inline void INIT_HLIST_NODE(struct hlist_node *h) {
    	h->next = NULL;
    	h->pprev = NULL;
    }
    
    static inline int hlist_unhashed(const struct hlist_node *h) {
    	return !h->pprev;
    }
    
    static inline int hlist_empty(const struct hlist_head *h) {
    	return !h->first;
    }
    
    static inline void __hlist_del(struct hlist_node *n) {
    	struct hlist_node *next = n->next;
    	struct hlist_node **pprev = n->pprev;
    	*pprev = next;
    	if (next)
    		next->pprev = pprev;
    }
    
    static inline void hlist_del(struct hlist_node *n) {
    	__hlist_del(n);
    	n->next = NULL;
    	n->pprev = NULL;
    }
    
    static inline void hlist_del_init(struct hlist_node *n) {
    	if (!hlist_unhashed(n)) {
    		__hlist_del(n);
    		INIT_HLIST_NODE(n);
    	}
    }
    
    static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h) {
    	struct hlist_node *first = h->first;
    	n->next = first;
    	if (first)
    		first->pprev = &n->next;
    	h->first = n;
    	n->pprev = &h->first;
    }
    
    /* next must be != NULL */
    static inline void hlist_add_before(struct hlist_node *n,
    		struct hlist_node *next) {
    	n->pprev = next->pprev;
    	n->next = next;
    	next->pprev = &n->next;
    	*(n->pprev) = n;
    }
    
    static inline void hlist_add_after(struct hlist_node *n,
    		struct hlist_node *next) {
    	next->next = n->next;
    	n->next = next;
    	next->pprev = &n->next;
    
    	if (next->next)
    		next->next->pprev = &next->next;
    }
    
    /*
     * Move a list from one list head to another. Fixup the pprev
     * reference of the first entry if it exists.
     */
    static inline void hlist_move_list(struct hlist_head *old,
    		struct hlist_head *new) {
    	new->first = old->first;
    	if (new->first)
    		new->first->pprev = &new->first;
    	old->first = NULL;
    }
    
    #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
    
    #define hlist_for_each(pos, head) \
    	for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
    	     pos = pos->next)
    
    #define hlist_for_each_safe(pos, n, head) \
    	for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
    	     pos = n)
    
    /**
     * hlist_for_each_entry	- iterate over list of given type
     * @tpos:	the type * to use as a loop cursor.
     * @pos:	the &struct hlist_node to use as a loop cursor.
     * @head:	the head for your list.
     * @member:	the name of the hlist_node within the struct.
     */
    #define hlist_for_each_entry(tpos, pos, head, member)			 \
    	for (pos = (head)->first;					 \
    	     pos && ({ prefetch(pos->next); 1;}) &&			 \
    		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
    	     pos = pos->next)
    
    /**
     * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
     * @tpos:	the type * to use as a loop cursor.
     * @pos:	the &struct hlist_node to use as a loop cursor.
     * @member:	the name of the hlist_node within the struct.
     */
    #define hlist_for_each_entry_continue(tpos, pos, member)		 \
    	for (pos = (pos)->next;						 \
    	     pos && ({ prefetch(pos->next); 1;}) &&			 \
    		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
    	     pos = pos->next)
    
    /**
     * hlist_for_each_entry_from - iterate over a hlist continuing from current point
     * @tpos:	the type * to use as a loop cursor.
     * @pos:	the &struct hlist_node to use as a loop cursor.
     * @member:	the name of the hlist_node within the struct.
     */
    #define hlist_for_each_entry_from(tpos, pos, member)			 \
    	for (; pos && ({ prefetch(pos->next); 1;}) &&			 \
    		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
    	     pos = pos->next)
    
    /**
     * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
     * @tpos:	the type * to use as a loop cursor.
     * @pos:	the &struct hlist_node to use as a loop cursor.
     * @n:		another &struct hlist_node to use as temporary storage
     * @head:	the head for your list.
     * @member:	the name of the hlist_node within the struct.
     */
    #define hlist_for_each_entry_safe(tpos, pos, n, head, member) 		 \
    	for (pos = (head)->first;					 \
    	     pos && ({ n = pos->next; 1; }) && 				 \
    		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
    	     pos = n)
    
    #endif /* HLIST_H_ */

    hash链表实例

    首先实现了自己的hash list初始化、键存在与否判定以及key值查找等函数。然后是主测试程序。

    #define MAX_LEN 20
    
    struct hash_node {
    	struct hlist_node hnode;
    	int age;
    };
    
    struct hlist_head hashead[MAX_LEN];
    
    void init_hlist() {
    	int i = 0;
    	for (i = 0; i < MAX_LEN; i++) {
    		INIT_HLIST_HEAD(&hashead[i]);
    	}
    }
    
    int key_exists(struct hlist_head *head, int key) {
    	struct hash_node * node;
    	struct hlist_node *hlistnode;
    	hlist_for_each_entry(node, hlistnode, head,hnode) {
    		if (node->age == key) {
    			return 1;
    		}
    	}
    	return 0;
    }
    
    struct hash_node * hlist_search(int age) {
    	struct hash_node *node, *data;
    	int i = 0;
    	struct hlist_node *hlistnode;
    	for (i = 0; i < MAX_LEN; i++) {
    		hlist_for_each_entry(node, hlistnode, &hashead[i],hnode) {
    			data = container_of(&node->hnode, struct hash_node, hnode);
    			if (data->age == age) {
    				return data;
    			}
    		}
    	}
    	return NULL;
    }
    
    void testhlist() {
    
    	init_hlist();
    	int i = 0;
    	struct hash_node * node;
    	struct hlist_node *hlistnode;
    
    	srand(time(NULL));
    	for (i = 0; i < 4 * MAX_LEN; i++) {
    		node = malloc(sizeof(struct hash_node));
    		INIT_HLIST_NODE(&node->hnode);
    		node->age = rand() % (4 * MAX_LEN);
    		if (key_exists(&hashead[node->age % MAX_LEN], node->age) == 0) {
    			hlist_add_head(&node->hnode, &hashead[node->age % MAX_LEN]);
    		}
    	}
    	for (i = 0; i < MAX_LEN; i++) {
    		printf("head %d has member :", i);
    		hlist_for_each_entry(node, hlistnode, &hashead[i],hnode) {
    			printf("%d  ", node->age);
    		}
    		printf("\n");
    	}
    
    	for (i = 0; i < MAX_LEN; i++) {
    		node = hlist_search(i);
    		if (NULL != node) {
    			printf("found %d\n", i);
    			hlist_del(&node->hnode);
    		}
    	}
    	printf("after clear \n");
    	for (i = 0; i < MAX_LEN; i++) {
    		printf("head %d has member :", i);
    		hlist_for_each_entry(node, hlistnode, &hashead[i],hnode) {
    			printf("%d  ", node->age);
    		}
    		printf("\n");
    	}
    
    }

    在main函数里,调用主测试程序即可。

    展开全文
  • 哈希表的地址链表

    千次阅读 2011-12-12 15:04:01
    散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组...
     
    

    散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

     

    下面的哈希表函数使用了(除留余数)

     

    头文件:HashTable.h

    #ifndef HASHTABLE_H
    #define HASHTABLE_H
    #define MAXSIZE 17
    #define NULLKEY -32768
    typedef struct node{ //关键字结点
    	int data;    //关键字
    	struct node *next;  //指向下一个结点
    }Node;
    typedef struct Table{
    	Node *table;  //动态分配哈希表
    	int count;    //哈希表的关键字个数
    }HashTable;
    
    void InitHashTable(HashTable *H); //初始化哈希表
    int Hash(int key);  //哈希表函数
    void InsertHashTable(HashTable *H,int key); //把关键字插入哈希表
    bool SearchHashTable(HashTable *H,int key); //在哈希表中查找关键字key
    #endif //HASHTABLE_H
    
    


    实现文件:HashTable.cpp

    #include "HashTable.h"
    #include <stdio.h>
    #include <stdlib.h>
    void InitHashTable(HashTable *H) //初始化哈希表
    {
    	H->count = MAXSIZE; //初始化哈希表的大小
    	H->table = (Node *)malloc(sizeof(Node) * H->count); //创建哈希表
    	for(int i = 0;i < H->count;++i) //初始化哈希表的数据
    	{
    		H->table[i].data = NULLKEY;
    		H->table[i].next = NULL;
    	}
    }
    int Hash(int key)  //哈希表函数
    {
    	return key % MAXSIZE;
    }
    void InsertHashTable(HashTable *H,int key) //将关键字key插入哈希表
    {
    	int addr = Hash(key);
    	if(H->table[addr].data != key && H->table[addr].data != NULLKEY) //如果为真,创建单链表
    	{
    		Node *temp = (Node *)malloc(sizeof(Node));
    		temp->next = H->table[addr].next;
    		temp->data = key;
    		H->table[addr].next = temp;
    	}
    	else if(H->table[addr].data == NULLKEY)  //则否直接填入
    		H->table[addr].data = key;
    }
    bool SearchHashTable(HashTable *H,int key) //查找关键字key的值
    {
    	int addr = Hash(key);
    	if(H->table[addr].data == key)
    		return true;
    	Node *p = H->table[addr].next;
    	while(p != NULL) //查找单链表
    	{
    		if(p->data == key)
    			return true;
    		else
    			p = p->next;
    	}
    	return false;
    }
    
    
    


    测试文件:main.cpp

    #include "HashTable.h"
    #include <stdio.h>
    int main()
    {
    	HashTable H;
    	InitHashTable(&H);
    	for(int i = 0;i < MAXSIZE * 2;i += 2)
    		InsertHashTable(&H,i);
    	printf("请输入要查找的内容:\n");
    	int key;
    	scanf("%d",&key);
    	if(SearchHashTable(&H,key))
    		printf("在哈希表中找到关键字:%d\n",key);
    	else
    		printf("在哈希表中未找到关键字:%d\n",key);
    	return 0;
    }
    


     

    展开全文
  • 哈希链表查找

    2018-05-26 20:04:25
    #define MAX 10 //链表数据结构 typedef struct list { int data; ... ///链式法解决地址冲突,MAX个带头节点的hash链表 //除留取余法 int hashFunc(int n) { return n%MAX; } //创建ha...
    #define MAX 10
            
    //链表数据结构
    typedef struct list  
    {
    	int data;
    	list *next;
    }*pList;
    
    list hashtable[MAX];  ///链式法解决地址冲突,MAX个带头节点的hash链表
    
    //除留取余法
    int hashFunc(int n)   
    {
    	return n%MAX;
    }
    
    //创建hash链表
    void createhash(int *array,int n)  
    {
    	pList p,pNew;
    	for (int i=0;i<n;i++)
    	{
    		pNew=new list;
    		pNew->data=array[i];
    		pNew->next=NULL;
    		
    		int pos=hashFunc(array[i]);
    		p=hashtable[pos].next;
    		
    		if (p!=NULL)         //将新的节点插入到头结点的后面
    		{
    			pNew->next=p;
    			hashtable[pos].next=pNew;
    		} 
    		else
    		{
    			hashtable[pos].next=pNew;
    		}
    	}
    }
    
    //hash查找
    bool SearchHash(int val)   
    {
    	int pos=hashFunc(val);        //找出在哪个hash链表
    	pList p=hashtable[pos].next;  //遍历对应的链表
    	while(p!=NULL)
    	{
    		if(p->data==val)
    			return true;
    		p=p->next;
    	}
    	
    	return false;
    }
    
    //遍历hashtable
    void TraverseHashtable()
    {
    	for (int m=0;m<MAX;m++) //一次遍历每个链表里面的内容
    	{
    		pList p1=hashtable[m].next;
    		while(p1!=NULL)
    		{
    			cout<<p1->data<<" ";
    			p1=p1->next;
    		}
    	}
    	cout<<endl;
    }

    展开全文
  • 数据结构之哈希表与链表、数组

    千次阅读 2018-09-26 10:43:35
    哈希表的内容主要转载自:博主名字太有特色没好意思写上来 哈希表 主要描述哈希表的定义:通过关键码寻找值的数据映射结构,类似于查字典 当存在哈希冲突时,有两种常用的方式:开发定址法和链地址法 ...
  • Hash链表

    2019-06-25 12:49:52
    <?... /* +------------------------------------------------------------------------------ | datetime 2013-10-29 12:46:44 ... +-------------------------------------------------------------...
  • HASH链表

    千次阅读 2019-05-13 13:06:47
    一,HASH链表与逻辑读 oracle要从高速缓冲区中拿到5号文件1234号块buffer的信息,就需要使用到HASH算法。 Buffer Cache:高速缓冲区中包含多个buffer,每一个buffer就记录一个数据块对应的缓冲信息。 Buffer Header:...
  • c语言实现hash map(链表散列hash

    千次阅读 2019-06-15 23:05:49
    散列(hash): 将字符串转换为固定长度的数组或索引值的方法,叫做散列法。 hashmap的底层结构 hashmap是一个链表散列的数据结构,即是数组和链表的结合体。(也可能是数组+链表+红黑树) 数组:存储空间连续,占用...
  • 我们都知道,链表是数据结构中用得最广泛的一种数据结构,对于数据结构,有顺序存储,数组就是一种。有链式存储,链表算一种。当然还有索引式的,散列式的,各种风格的说法,叫法层出不穷,但是万变不离其中,只要...
  • Linux 内核链表移植

    千次阅读 2013-04-24 10:47:31
    Linux 内核链表移植我参考网上的文章修改了移植后的Linux内核的双向链表和HASH链表, 使之适用于Linux和Windows平台. 可以在用户态下使用. 任何后果, 本人概不负责!下面是全部代码:/** * dhlist.h * - deque list ...
  • 双端链表实现hash(哈希)

    千次阅读 2015-12-09 18:39:26
    hash表又称为散列表,很多的地方都用到了这个东西,js中的对象,java中的键值对,python中的字典,hash结合了数组和链表的优点,在查找,存储有很大的优势。以我的理解来说,通过相应的键,找到相对应的值,数组的...
  • 刚刚看了java集合 有些不懂的地方 链表为什么有利于增删 hash表为什么有利于改查
  • 数组、链表Hash的优缺点

    千次阅读 2017-10-17 11:44:44
    IOS笔试题总结(数组、链表Hash的优缺点) 转载2016-04-22 17:08:33 数组、链表Hash的优缺点: 1、数组是将元素在内存中连续存放。  链表中的元素在内存中不是顺序存储的,而是通过存在元素中...
  • 146. LRU Cache hash+链表

    2017-03-16 22:50:30
    题目地址使用了一个hash表和一个链表,每次访问元素(get)或是添加元素都将元素置于链表的头部,尾部的自然就是最久未使用的。 hash表存储元素在链表中的位置,链表储存key-value,以方便超出容量时从hash表移除旧...
  • From: 全面解析Linux 内核 3.10.x - 进程管理 不管千山万水,时间流逝,我们始终是有关系的 - 某某言情剧何谓进程之间的关系?在前面作总结的时候,说进程有一个标识ID,我们称之为进程描述符,描述符描述了进程的...
  • 链表 废话不多说,今天继续学习Redis的基本数据结构——链表和哈希表。 先看一个例子,以下展示的integers列表键包含了从1到1024共一千零二十四个整数: redis-&gt; LLEN integers (integer) 1024 redis-&...
  • 字符串的经典hash算法

    2017-04-17 21:17:58
    设计高效算法往往需要使用Hash链表,常数级的查找速度是任何别的算法无法比拟的,Hash链表的构造和冲突的不同实现方法对效率当然有一定的影响,然而Hash函数是Hash链表最核心的部分,本文尝试分析一些经典软件中使用...
  • linux内核哈希链表解析

    千次阅读 2016-02-26 09:06:20
    linux内核里边除了著名的list双向循环链表以外,还有一个重要的数据结构,就是哈希链表。哈希链表也在很多重要的地方有所使用,比如linux内核的dentry,进程查询,文件系统等,可以说,弄明白hlist对于理解linux内核...
  • hash是以空间换时间的结构,现在空间越来越大,而且对性能要求越来越高的年代,这绝对是值得的。...hash函数的选择必须慎重,如果不幸所有的元素之间都产生了冲突,那么hash表将退化为链表,其性能会大打折扣,时间...
  • 为了较快的从给定的pid值得到相应的宿主结构(进程描述符)指针,内核采用了pid哈希链表结构。 首先,以下的问题要理解: 1)为什么pid哈希链表只定义2048或者4096项(根据你的内存大小确定)?直接定义为pid最大...
1 2 3 4 5 ... 20
收藏数 126,558
精华内容 50,623
关键字:

hash链表