散列存储方法 _百度百科
特色百科用户权威合作手机百科
收藏 查看&散列存储方法本词条缺少概述、信息栏、名片图，补充相关内容使词条更完整，还能快速升级，赶紧来吧！
散列存储，又称hash存储，是一种力图将的存储hash位置与关键码之间建立确定对应关系的查找技术。存储的基本思想是：由的关键码值决定节点的存储地址。散列技术除了可以用于查找外，还可以用于存储。散列是数组存储方式的一种发展，相比数组，散列的数据访问速度要高于数组，因为可以依据存储数据的部分内容找到数据在数组中的存储位置，进而能够快速实现数据的访问，理想的散列访问速度是非常迅速的，而不像在数组中的遍历过程，采用存储数组中内容的部分元素作为映射函数的输入，映射函数的输出就是存储数据的位置，这样的访问速度就省去了遍历数组的实现，因此时间复杂度可以认为为O(1)，而数组遍历的时间复杂度为O(n)。
散列是能一种快速实现访问的存储方式。通常作为检索部分的数据项是整形或者字符串，当是字符串时，字符串的数量要远远大于数组的长度，这时候就会有多个字符串映射到一个存储位置的情况，这就是所谓的冲突问题，而且冲突时肯定存在的，这时候如何实现数据的存储又是需要解决的。目前主要的解决方式有两大类，第一种采用链表的形式，将所有冲突的数据项采用链表的形式链接起来，这样搜索数据的复杂度就包含了链表的遍历问题，特别是当所有的项都链接到一个链表下时，这时候实际上就是遍历链表，复杂度并不一定有很大的进步，但是这种链表链接的方式有很高的填充率。第二种就是充分利用没有实现的存储空间，利用探测法探测空闲的空间，进而实现数据的存储，目前有三种探测方式：线性探测法、平方探测法，以及双散列法，三种方式中平方探测法运用比较多，但是都存在各种各样的优缺点，这时候的散列搜索优势就没有理想情况下那么明显。有时候甚至比遍历数组更加的慢。但是确实不失为一种处理方式。映射函数可选择的比较多，其实完全可以定义自己的映射函数，但是有时候为了降低冲突的概率设置了一些比较好的映射函数，比如求和取余，或者乘以一定的系数再求和取余等。
本文采用平方探测法解决了冲突问题，具体的实现如下所示：
1、结构体定义
#ifndef__HASHMAP_H_H_
#define__HASHMAP_H_H_
#include&list.h&
#defineTABSIZE101
/*状态变量*/
typedefenumSTATE{EMPTY=0,ACTIVE=1,DELETED=2}S
/*键值结构体*/
typedefstruct_pair
}Pair_t,*Pair_handle_t;
/*每一个实际的存储对象*/
typedefstruct_hashEntry
Pair_handle_
}HashEntry_t,*HashEntry_handle_t;
/*哈希表结构体，便于创建*/
typedefstruct_hashmap
HashEntry_t*
/*存储实际的存储量*/
}Hashmap_t,*Hashmap_handle_t;
/*隐射函数类型定义*/
typedefint(*hashfunc)(constchar*,int);
#ifdef__cplusplus
boolalloc_hashmap(Hashmap_handle_t*hashmap,intcapacity);
boolinit_hashmap(Hashmap_handle_thashmap,intcapacity);
boolinsert_hashnode(Hashmap_handle_thashmap,constchar*key,constchar*value);
Pair_handle_tsearch_hashnode(Hashmap_handle_thashmap,constchar*key);
char*GetValue(Hashmap_handle_thashmap,constchar*key);
booldelete_hashnode(Hashmap_handle_thashmap,constchar*key);
intLength(Hashmap_handle_thashmap);
intCapacity(Hashmap_handle_thashmap);
voiddelete_hashmap(Hashmap_handle_thashmap);
voidfree_hashmap(Hashmap_handle_t*hashmap);
char*key_pair(Pair_handle_tpair);
char*value_pair(Pair_handle_tpair);
Hashmap_handle_tcopy_hashmap(Hashmap_handle_thashmap);
boolresize(Hashmap_handle_thashmap);
#ifdef__cplusplus
实现表的分配和创建，采用了动态分配的方式实现，这样可能在性能上比不上静态数据，但是为了实现数组大小的调整，我选择了动态分配的实现方式。
/*分配一个新的对象，可以实现自动分配*/
boolalloc_hashmap(Hashmap_handle_t*hashmap,intcapacity)
HashEntry_handle_ttemp=NULL;
Hashmap_t*map=NULL;
if(*hashmap==NULL)
/*分配一个散列对象*/
map=(Hashmap_handle_t)malloc(sizeof(Hashmap_t));
if(map==NULL)
/*指针指向当前对象*/
/*分配一个数组空间，大小可以控制*/
temp=(HashEntry_handle_t)malloc(
sizeof(HashEntry_t)*capacity);
if(temp!=NULL)
/*散列对象的指针指向数组*/
(*hashmap)-&map=
temp=NULL;
/*设置参数*/
(*hashmap)-&capacity=
(*hashmap)-&size=0;
/*初始化分配的数组空间*/
Tabinital((*hashmap)-&map,capacity);
/*初始化一个新的对象，这个对象已经创建，只是没有初始化而已*/
boolinit_hashmap(Hashmap_handle_thashmap,intcapacity)
HashEntry_handle_ttemp=NULL;
if(hashmap!=NULL)
/*分配数组空间*/
temp=(HashEntry_handle_t)malloc(
sizeof(HashEntry_t)*capacity);
if(temp!=NULL)
/*完成对象的填充操作*/
hashmap-&map=
temp=NULL;
hashmap-&capacity=
hashmap-&size=0;
/*初始化数组对象*/
Tabinital(hashmap-&map,capacity);
关于数组中对象的创建，和释放操作，如下所示：
/*分配一个pair对象*/
staticboolmake_pair(Pair_handle_t*pair,constchar*key,constchar*value)
Pair_handle_tnewpair=(Pair_handle_t)malloc(sizeof(Pair_t));
char*newstr=NULL;
if(newpair==NULL)
newstr=(char*)malloc(strlen(key)+1);
if(newstr==NULL)
strcpy(newstr,key);
newstr[strlen(key)]='\0';
newpair-&key=
newstr=NULL;
newstr=(char*)malloc(strlen(value)+1);
if(newstr==NULL)
strcpy(newstr,value);
newstr[strlen(value)]='\0';
newpair-&value=
newstr=NULL;
/*释放一个对象pair*/
staticvoiddelete_pair(Pair_handle_t*pair)
Pair_handle_ttemp=NULL;
if(*pair==NULL)
free(temp-&key);
temp-&key=NULL;
free(temp-&value);
temp-&value=NULL;
free(temp);
temp=NULL;
*pair=NULL;
数组元素的基本操作：
/*完成数组对象的初始化操作*/
staticvoidTabinital(HashEntry_t*tab,intsize)
tab[i].pair=NULL;
tab[i].state=EMPTY;
staticvoiddelete_array(HashEntry_handle_t*array,intsize)
if(*array!=NULL)
if((*array)[i].state==ACTIVE)
delete_pair(&((*array)[i].pair));
(*array)[i].state=DELETED;
free(*array);
*array=NULL;
插入元素的操作、有两个函数的创建，其中一个为了便于后期大小的调整操作。
/*插入数据到散列中，采用了二次探测的实现方式，并设置了退出条件*/
staticboolinsert_data(Hashmap_handle_thashmap,
constchar*key,constchar*value,hashfuncfunc)
inthashval=func(key,hashmap-&capacity);
intindex=0;
char*newstr=NULL;
Pair_handle_tnewpair=NULL;
while(hashmap-&map[hashval].state!=EMPTY)
if((hashmap-&map[hashval].state==ACTIVE)
&&(strcmp(hashmap-&map[hashval].pair-&key,key)==0))
hashval+=index*
hashval%=hashmap-&
if(index==200)
if(hashmap-&map[hashval].state==EMPTY)
if(make_pair(&newpair,key,value))
hashmap-&map[hashval].state=ACTIVE;
hashmap-&map[hashval].pair=
newpair=NULL;
hashmap-&size++;
数据在计算机中存储的有四种：顺序、、散列与索引。散列是由单词Hash翻译过来的，有时也直接音译为“哈希”，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。
新手上路我有疑问投诉建议参考资料 查看1. LinkedHashMap概述：
LinkedHashMap是HashMap的一个子类，它保留插入的顺序，如果需要输出的顺序和输入时的相同，那么就选用LinkedHashMap。
&& LinkedHashMap是Map接口的哈希表和链接列表实现，具有可预知的迭代顺序。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。&& LinkedHashMap实现与HashMap的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。&& 注意，此实现不是同步的。如果多个线程同时访问链接的哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须保持外部同步。
根据链表中元素的顺序可以分为：按插入顺序的链表，和按访问顺序(调用get方法)的链表。&&
默认是按插入顺序排序，如果指定按访问顺序排序，那么调用get方法后，会将这次访问的元素移至链表尾部，不断访问可以形成按访问顺序排序的链表。 &可以重写removeEldestEntry方法返回true值指定插入元素时移除最老的元素。&
2. LinkedHashMap的实现：
&& 对于LinkedHashMap而言，它继承与HashMap、底层使用哈希表与双向链表来保存所有元素。其基本操作与父类HashMap相似，它通过重写父类相关的方法，来实现自己的链接列表特性。下面我们来分析LinkedHashMap的源代码：
Java代码&&
public&class&LinkedHashMap&K,&V&&extends&HashMap&K,&V&&implements&Map&K,&V&&&&&
&1) 成员变量：
&& LinkedHashMap采用的hash算法和HashMap相同，但是它重新定义了数组中保存的元素Entry，该Entry除了保存当前对象的引用外，还保存了其上一个元素before和下一个元素after的引用，从而在哈希表的基础上又构成了双向链接列表。看源代码：
Java代码&&
&private&final&boolean&accessO&&
private&transient&Entry&K,V&&&&
private&static&class&Entry&K,V&&extends&HashMap.Entry&K,V&&{&&
&&&&Entry&K,V&&before,&&&
HashMap.Entry:
Java代码&&
static&class&Entry&K,V&&implements&Map.Entry&K,V&&{&&
&&&&&&&&final&K&&&
&&&&&&&&V&&&
&&&&&&&&Entry&K,V&&&&
&&&&&&&&final&int&&&
&&&&&&&&Entry(int&h,&K&k,&V&v,&Entry&K,V&&n)&{&&
&&&&&&&&&&&&value&=&v;&&
&&&&&&&&&&&&next&=&n;&&
&&&&&&&&&&&&key&=&k;&&
&&&&&&&&&&&&hash&=&h;&&
&&&&&&&&}&&
&&&&2) 初始化：
&& 通过源代码可以看出，在LinkedHashMap的构造方法中，实际调用了父类HashMap的相关构造方法来构造一个底层存放的table数组。如：
public&LinkedHashMap(int&initialCapacity,&float&loadFactor)&{&&
&&&&super(initialCapacity,&loadFactor);&&
&&&&accessOrder&=&false;&&
&&& HashMap中的相关构造方法：
public&HashMap(int&initialCapacity,&float&loadFactor)&{&&
&&&&if&(initialCapacity&&&0)&&
&&&&&&&&throw&new&IllegalArgumentException("Illegal&initial&capacity:&"&+&&
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&initialCapacity);&&
&&&&if&(initialCapacity&&&MAXIMUM_CAPACITY)&&
&&&&&&&&initialCapacity&=&MAXIMUM_CAPACITY;&&
&&&&if&(loadFactor&&=&0&||&Float.isNaN(loadFactor))&&
&&&&&&&&throw&new&IllegalArgumentException("Illegal&load&factor:&"&+&&
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&loadFactor);&&
&&&&int&capacity&=&1;&&
&&&&while&(capacity&&&initialCapacity)&&
&&&&&&&&capacity&&&=&1;&&
&&&&this.loadFactor&=&loadF&&
&&&&threshold&=&(int)(capacity&*&loadFactor);&&
&&&&table&=&new&Entry[capacity];&&
&&&&init();&&
&&& 我们已经知道LinkedHashMap的Entry元素继承HashMap的Entry，提供了双向链表的功能。在上述HashMap的构造器中，最后会调用init()方法，进行相关的初始化，这个方法在HashMap的实现中并无意义，只是提供给子类实现相关的初始化调用。&& LinkedHashMap重写了init()方法，在调用父类的构造方法完成构造后，进一步实现了对其元素Entry的初始化操作。
void&init()&{&&
&&&&header&=&new&Entry&K,V&(-1,&null,&null,&null);&&
&&&&header.before&=&header.after&=&&&
&&&&3) 存储：
&&&LinkedHashMap并未重写父类HashMap的put方法，而是重写了父类HashMap的put方法调用的子方法void recordAccess(HashMap m)&& ，void addEntry(int hash, K key, V value, int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex)，提供了自己特有的双向链接列表的实现。
HashMap.put:
Java代码&&
public&V&put(K&key,&V&value)&{&&
&&&&&&&&if&(key&==&null)&&
&&&&&&&&&&&&return&putForNullKey(value);&&
&&&&&&&&int&hash&=&hash(key.hashCode());&&
&&&&&&&&int&i&=&indexFor(hash,&table.length);&&
&&&&&&&&for&(Entry&K,V&&e&=&table[i];&e&!=&null;&e&=&e.next)&{&&
&&&&&&&&&&&&Object&k;&&
&&&&&&&&&&&&if&(e.hash&==&hash&&&&((k&=&e.key)&==&key&||&key.equals(k)))&{&&
&&&&&&&&&&&&&&&&V&oldValue&=&e.&&
&&&&&&&&&&&&&&&&e.value&=&&&
&&&&&&&&&&&&&&&&e.recordAccess(this);&&
&&&&&&&&&&&&&&&&return&oldV&&
&&&&&&&&&&&&}&&
&&&&&&&&}&&
&&&&&&&&modCount++;&&
&&&&&&&&addEntry(hash,&key,&value,&i);&&
&&&&&&&&return&null;&&
&重写方法：
Java代码&&
void&recordAccess(HashMap&K,V&&m)&{&&
&&&&&&&&&&&&LinkedHashMap&K,V&&lm&=&(LinkedHashMap&K,V&)m;&&
&&&&&&&&&&&&if&(lm.accessOrder)&{&&
&&&&&&&&&&&&&&&&lm.modCount++;&&
&&&&&&&&&&&&&&&&remove();&&
&&&&&&&&&&&&&&&&addBefore(lm.header);&&
&&&&&&&&&&&&}&&
&&&&&&&&}&&
void&addEntry(int&hash,&K&key,&V&value,&int&bucketIndex)&{&&
&&&&createEntry(hash,&key,&value,&bucketIndex);&&
&&&&Entry&K,V&&eldest&=&header.&&
&&&&if&(removeEldestEntry(eldest))&{&&
&&&&&&&&removeEntryForKey(eldest.key);&&
&&&&}&else&{&&
&&&&&&&&if&(size&&=&threshold)&&
&&&&&&&&&&&&resize(2&*&table.length);&&
void&createEntry(int&hash,&K&key,&V&value,&int&bucketIndex)&{&&
&&&&HashMap.Entry&K,V&&old&=&table[bucketIndex];&&
&&&&Entry&K,V&&e&=&new&Entry&K,V&(hash,&key,&value,&old);&&
&&&&table[bucketIndex]&=&e;&&
&&&&e.addBefore(header);&&
&&&&size++;&&
private&void&addBefore(Entry&K,V&&existingEntry)&{&&
&&&&after&&=&existingE&&
&&&&before&=&existingEntry.&&
&&&&before.after&=&this;&&
&&&&after.before&=&this;&&
&& LinkedHashMap重写了父类HashMap的get方法，实际在调用父类getEntry()方法取得查找的元素后，再判断当排序模式accessOrder为true时，记录访问顺序，将最新访问的元素添加到双向链表的表头，并从原来的位置删除。由于的链表的增加、删除操作是常量级的，故并不会带来性能的损失。
HashMap.containsValue:
Java代码&&
public&boolean&containsValue(Object&value)&{&&
&&&&if&(value&==&null)&&
&&&&&&&&&&&&return&containsNullValue();&&
&&&&Entry[]&tab&=&&&
&&&&&&&&for&(int&i&=&0;&i&&&tab.length&;&i++)&&
&&&&&&&&&&&&for&(Entry&e&=&tab[i]&;&e&!=&null&;&e&=&e.next)&&
&&&&&&&&&&&&&&&&if&(value.equals(e.value))&&
&&&&&&&&&&&&&&&&&&&&return&true;&&
&&&&return&false;&&
Java代码&&
public&boolean&containsValue(Object&value)&{&&
&&&&&&&&&&
&&&&&&&&if&(value==null)&{&&
&&&&&&&&&&&&for&(Entry&e&=&header.&e&!=&&e&=&e.after)&&
&&&&&&&&&&&&&&&&if&(e.value==null)&&
&&&&&&&&&&&&&&&&&&&&return&true;&&
&&&&&&&&}&else&{&&
&&&&&&&&&&&&for&(Entry&e&=&header.&e&!=&&e&=&e.after)&&
&&&&&&&&&&&&&&&&if&(value.equals(e.value))&&
&&&&&&&&&&&&&&&&&&&&return&true;&&
&&&&&&&&}&&
&&&&&&&&return&false;&&
Java代码&&
&void&transfer(HashMap.Entry[]&newTable)&{&&
&&&int&newCapacity&=&newTable.&&
&&&for&(Entry&K,&V&&e&=&header.&e&!=&&e&=&e.after)&{&&
&&&&&int&index&=&indexFor(e.hash,&newCapacity);&&
&&&&&e.next&=&newTable[index];&&
&&&&&newTable[index]&=&e;&&
public&V&get(Object&key)&{&&
&&&&Entry&K,V&&e&=&(Entry&K,V&)getEntry(key);&&
&&&&if&(e&==&null)&&
&&&&&&&&return&null;&&
&&&&e.recordAccess(this);&&
&&&&return&e.&&
void&recordAccess(HashMap&K,V&&m)&{&&
&&&&LinkedHashMap&K,V&&lm&=&(LinkedHashMap&K,V&)m;&&
&&&&if&(lm.accessOrder)&{&&
&&&&&&&&lm.modCount++;&&
&&&&&&&&remove();&&
&&&&&&&&addBefore(lm.header);&&
Java代码&&
&&&&&&&&private&void&remove()&{&&
&&&&&&&&&&&&before.after&=&&&
&&&&&&&&&&&&after.before&=&&&
&&&&&&&&}&&
Java代码&&
public&void&clear()&{&&
&super.clear();&&
&header.before&=&header.after&=&&&
&&&&5) 排序模式：
&& LinkedHashMap定义了排序模式accessOrder，该属性为boolean型变量，对于访问顺序，为true；对于插入顺序，则为false。
private&final&boolean&accessO&&
&一般情况下，不必指定排序模式，其迭代顺序即为默认为插入顺序。看LinkedHashMap的构造方法，如：
public&LinkedHashMap(int&initialCapacity,&float&loadFactor)&{&&
&&&&super(initialCapacity,&loadFactor);&&
&&&&accessOrder&=&false;&&
&&& 这些构造方法都会默认指定排序模式为插入顺序。如果你想构造一个LinkedHashMap，并打算按从近期访问最少到近期访问最多的顺序（即访问顺序）来保存元素，那么请使用下面的构造方法构造LinkedHashMap：
public&LinkedHashMap(int&initialCapacity,&&
&&&&&&&&&float&loadFactor,&&
&&&&&&&&&&&&&&&&&&&&&boolean&accessOrder)&{&&
&&&&super(initialCapacity,&loadFactor);&&
&&&&this.accessOrder&=&accessO&&
&&& 该哈希映射的迭代顺序就是最后访问其条目的顺序，这种映射很适合构建LRU缓存。LinkedHashMap提供了removeEldestEntry(Map.Entry&K,V& eldest)方法。该方法可以提供在每次添加新条目时移除最旧条目的实现程序，默认返回false，这样，此映射的行为将类似于正常映射，即永远不能移除最旧的元素。
当有新元素加入Map的时候会调用Entry的addEntry方法，会调用removeEldestEntry方法，这里就是实现LRU元素过期机制的地方，默认的情况下removeEldestEntry方法只返回false表示元素永远不过期。
Java代码& &
&&&void&addEntry(int&hash,&K&key,&V&value,&int&bucketIndex)&{&&
&&&&&&&createEntry(hash,&key,&value,&bucketIndex);&&
&&&&&&&Entry&K,V&&eldest&=&header.&&
&&&&&&&if&(removeEldestEntry(eldest))&{&&
&&&&&&&&&&&removeEntryForKey(eldest.key);&&
&&&&&&&}&else&{&&
&&&&&&&&&&&if&(size&&=&threshold)&&&
&&&&&&&&&&&&&&&resize(2&*&table.length);&&
&&&&&&&}&&
&&&void&createEntry(int&hash,&K&key,&V&value,&int&bucketIndex)&{&&
&&&&&&&HashMap.Entry&K,V&&old&=&table[bucketIndex];&&
Entry&K,V&&e&=&new&Entry&K,V&(hash,&key,&value,&old);&&
&&&&&&&table[bucketIndex]&=&e;&&
&&&&&&&e.addBefore(header);&&
&&&&&&&size++;&&
&&&protected&boolean&removeEldestEntry(Map.Entry&K,V&&eldest)&{&&
&&&&&&&return&false;&&
此方法通常不以任何方式修改映射，相反允许映射在其返回值的指引下进行自我修改。如果用此映射构建LRU缓存，则非常方便，它允许映射通过删除旧条目来减少内存损耗。
&& 例如：重写此方法，维持此映射只保存100个条目的稳定状态，在每次添加新条目时删除最旧的条目。
private&static&final&int&MAX_ENTRIES&=&100;&&
protected&boolean&removeEldestEntry(Map.Entry&eldest)&{&&
&&&&return&size()&&&MAX_ENTRIES;&&
部分修改。
使用LinkedHashMap构建LRU的Cache
基于LinkedHashMap实现LRU缓存调度算法原理及应用
其实LinkedHashMap几乎和HashMap一样，不同的是它定义了一个Entry&K,V& header，这个header不是放在Table里，它是额外独立出来的。LinkedHashMap通过继承hashMap中的Entry&K,V&,并添加两个属性Entry&K,V& &before,after,和header结合起来组成一个双向链表，来实现按插入顺序或访问顺序排序。
阅读(...) 评论()