Posted by conan | Posted in 读书笔记 | Posted on 10-09-2009
哈希算法，用一个算式result=hash(key)就可以大致确定所需数据的位置，大大简化了数据查找的复杂度。此算法的关键在于建立一种两类数据间的映射，就是那个hash函数的选定。另外有个很重要的问题就是hash冲突，就是不同的key得到了同样的result。常用冲突解决法有拉链法（我认为叫做链表法更容易理解）和平面地址法两种，后面有描述。
c语言宏处理器（出自C程序设计语言）
“这段代码很典型，可以在宏处理器或编译器的符号表管理例程中找到。”
例如考虑define语句。
#define IN 1
需要把名字IN和替换文本1存入到某个表中，此后当名字IN出现在某些语句中时，就必须用1来替换IN。
以下两个函数用来处理名字和替换文本。install(s, t)函数将名字s和替换文本t记录到某个表中，其中s和他仅仅是字符串。lookup(s)函数在表中查找s，若找到，则返回指向该处的指针；若没找到，返回NULL。
该算法采用的是散列查找方法，将输入的名字转换为一个小的非负整数，该整数随后将作为一个指针数组的下标。数组的每个元素指向某个链表的表头，链表中的各个块用于描述具有该散列值的名字。如果没有名字散列到该值，则数组元素值为NULL。
链表块结构：
struct nlist { /*链表项*/
struct nlist *next; /*链表中下一表项*/
char *name; /*定义的名字*/
char *defn; /*替换文本*/
}
指针数组：
#define HASHSIZE 101
static struct nlist *hashtab[HASHSIZE]; /*指针表*/
散列函数hash，通过for循环将上次计算的结果值变换（乘以31）得到的值加上当前字符值（*s + 31 * hashval），然后对数组长度取模。这并不是最好的散列函数，但比较简短有效。
unsigned hash(char *s)
{
unsigned hashval;
for (hashval = 0; *s != ”; s++)
hashval = *s + 31 * hashval;
return hashval % HASHSIZE;
}
strdup函数将通过参数传入的字符串复制到某个安全的位置
char *strdup(char *s)
{
char *p;
p = (char *) malloc(strlen(s) + 1);
if (p != NULL)
strcpy(p, s);
return p;
}
lookup函数发现表项存在，则返回指向该表项的指针，否则返回NULL。散列过程生成了在数组hashtab中执行查找的起始下标，若该字符串可以找到，则它一定位于该起始下标指向的链表的某个块中。
struct nlist *lookup(char *s)
{
struct nlist *np;
for (np = hashtab[hash(s)]; np != NULL; np = np-> next)
if (strcmp(s, np->name == 0))
return np; /*found*/
return NULL; /*not found*/
}
install函数借助lookup判断待加入的名字是否已经存在。若存在则用新的定义取而代之；否则创建新表项。若无足够空间创建新表项，则install函数返回NULL
struct nlist *lookup(char *);
char *strdup(char *);
struct nlist *install(char *name, char *defn)
{
struct nlist *np;
unsigned hashval;
if ((np = lookup(name)) == NULL){ /*not found*/
np = (struct nlist *) malloc(sizeof(*np));
if (np == NULL || (np->name = strdup(name)) == NULL)
return NULL;
hashval = hash（name）;
np->next = hashtab[hashval];
hashtab[hashval] = np;
} else /*already exist*/
free((void *) np->defn); /*free previous defn*/
if ((np->defn = strdup(defn)) == NULL)
return NULL;
return np;
}
三点疑问：
1.hash函数如何选的？
2.hashsize如何选定？
3.作为宏处理器，又用了宏定义？
Python字典类（代码之美 第18章）
“字典是python语言的基本数据类型，它的作用就像awk里的关联数组或者perl里的哈希表”
python的字典类实现中一般有以下内容：
int ma_fill 13
int ma_used 13
int ma_mask 31
PyDictEntry ma_table[]:
[0]: aa, 1 hash(aa) == -1549758592, -1549758592 & 31 = 0
.
.
.
域成员的名字前缀ma_的意思是映射，在Python里它专指那些提供关键字/数据元素匹配功能的数据结构。域成员：
ma_used 有关键字的存储单元数量。加入关键字增1，删除减一。
ma_fill 有关键字存储单元和哑存储单元的总数。删除关键字的时候不变化
ma_mask 对应哈希表大小的比特掩码。哈希表有ma_mask+1个存储单元。规定存储单元数永远是2的幂，那么ma_mask就是2**n – 1
ma_table 指向PyDictEntry结构的数组。这个结构包含几个指针，分别指向关键字对象，数据元素对象，保存关键字哈希值的缓存。缓存哈希值是为了提高速度，如字典大小变化的时候。
为小哈希表而做的特别优化
PyDictObject还包括一个拥有8个存储单元 的哈希表。不多于5个元素的小字典可以直接放在这张表内，从而免去了调用malloc（）的额外开销。同时这样做还提高了缓存的局部性，拿x86 GCC编译的PyDictObject来说，它的大小是124字节，刚好可以放进两个大小为64字节的缓存行。因为一般参数关键字用到的字典大部分都只包 含1到3个关键字，所以小哈希表的这种优化措施也提高了函数调用的性能。
为字符串关键字优化
一个字典里可以包括多种数据类型的关键字。不过在大多数Python程序的类实例和模块中，它们内部字典只用字符串做关键字。
首先，字符串比较时不会抛出异常，所以可以掠过一些不必要的错误检查。其次，比较两个字符串是比较简单的事，不像一般Python对象可能会有<, >, <=, >=, ==和!=这样的比较操作。
Java版优化：
Python的Java版本，Jython有一个专用字符串的字典类型：org.python.org.PyStringMap。而用 户编程时所用的字典类实际上是另外一个叫做org.python.core.PyDictionary的类型，内部使用 java.util.Hashtable类来保存内容，并加了一个简介层来提供子类化能力。Python不允许用户用其它数据类型替换内建的 __dict__字典类，从而免去了子类化的麻烦（有什么麻烦？不明白）。对Jython来说，有一个专门的字符串类型字典还是有意义的。
C版优化：动态选择存储方法
一开始，字典调用之处理字符串的方法，当用户需要检索非字符串数据类型时，就调用能够处理通用数据类型的方法。 PyDictObject只有一个域成员ma_lookup，他是一个函数指针
struct PyDictObject{
…
PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
}
字典类通过（dict->ma_lookup）(dict, key, hash)来查找关键字，里面的参数key是一个指针，它指向代表关键字的PyObject，参数hash是根据关键字算出来的哈希值。刚开始 时，ma_lookup指向函数lookdict_string，这个函数假定字典里所包含的关键字和待检索的关键字都是字符串类型的，用结构 PyStringObject表示。如果字典里有非字符串类型的关键字，或是用户想查找这样的关键字时，ma_lookup就会改成指向更加通用的查表函 数。当lookdict_string函数发现其参数的实际类型不是字符串时，它就会修改ma_lookup，并调用新的函数来进行查找。（这就是说，如 果你对一个纯字符串版本的字典进行非字符串检索时，比如d.get(1)，整体检索速度会比通用的情况要慢，哪怕这是一次失败查询。接下来字典的检索函数 就会切换到通用版本。这时候就算查的还是字符串类型的关键字，查询速度已经不能跟纯字符串版本同日而语了。）PyStringObject类型的子类应该 被认为时非字符串类型，因为子类里可能会定义相等比较操作。
冲突处理
拉链法：由于建立链表需要为每个链表元素申请内存空间，而内存分配比较慢。同时，遍历链表有可能会降低缓存局部性。此法被Python弃用。
开放地址法：如果第一次在存储单元i中没有找到待查关键字，那就按照某种固定的模式尝试其他存储单元。
/* 起始存储单元 */
slot = hash;
/* 初始干扰值 */
perturb = hash;
while (<存储单元非空> && <单元内的值不等于关键字值>){
slot = (5*slot) + 1 + perturb;
perturb >>= 5;
}
在c语言的代码里，5*slot可以用位运算和加法来替代：(slot<<2) + slot 。一开始，干扰因子perturb直接取成哈希值；接下来，他的二进制值在每次循环的时候右移5位。移位操作可以让哈希值的每个比特都能够迅速地参与到探 索尝试的计算中。经过若干次移位操作，干扰因子最终会变为0，此时探索模式就退化为slot=(5*slot)+1，它生成的数值可以使0和 ma_mask之间的任何一个数。因此，这种尝试模式可以确保：要么是找到关键字（如果是在检索字典），要么是找到一个空的存储单元（如果是准备向字典里 插入数据）。
每次偏移量5比特是根据试验得出来的。 跟4和6相比，5可以把冲突率再降低一点（Objects/dictobject.c里有大段的注释详细讨论了这种优化的前世今生。）
调整大小
关于关键字数量，现在的做法是保证哈希表最多有三分之二是满的。这个比例是折中的结果：太满就会导致更多的冲突，太稀疏就会浪费太多内存，同时也不利于缓存处理。
确定新尺寸
不超过5万个关键字的中小规模哈希表，新的尺寸应该是ma_used*4。大多数使用大字典的Python程序都会在初始阶段构建字 典，接下来做的就只是检索关键字或者是遍历字典。这时4倍会让字典显得有点稀疏（1/4的存储单元有数据），好处是在初始阶段构建字典时减少了字典调整的 次数。对于超过5w个关键字的大型字典，规定新尺寸是ma_used*2，可以避免浪费过多的内存空间。
一个合算的内存折中方案：空闲列表
Python在用参数关键字作函数调用时，会创建字典实例，然后在函数返回时销毁它们。这种操作发生的很频繁，字典实例的生命周期也很短。这种情况的一个有效优化措施是回收那些不再使用的数据结构。
Python用一个叫做free_dicts的数组来保存不再使用的字典。在Python 2.5中，这个数组长度是80.当需要创建PyDictObject时，Python会设法从free_dicts里找到一个指针，重用它指向的数据结 构。当字典被删除时， 它们就会被加到free_dicts数组中。如果此时数组已经满了，那就直接释放这个字典对象。
迭代和动态变化
在遍历迭代的过程中，Python不允许增加或者删除字典的存储单元。 当iter*（）系列方法第一次被调用时，迭代器会记住字典中所有元素的个数。如果在遍历迭代过程中，字典大小发生变化，迭代器就会抛出 RuntimeError异常，告诉用户：“迭代过程中字典的大小发生了变化”。
This work, unless otherwise expressly stated, is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.
Вы можете обратиться к нам за консультацией http://advokats.info/ по любому юридическому вопросу в любых отраслях права.
Сплит – системы в Волжском http://www.ciklonclimat.ru/ , Волгограде и Волгоградской области.
«IT-People» Продажа 1С; Обслуживание компьютерной техники; проектирование компьютерных сетей; телефония; создание и продвижение сайтов; поставка оборудования и ПО; 152-ФЗ; контроль доступа; видеонаблюдение; Аутсорсинг — IT-people – 1С Франчайзи, ИТ решения. http://it-ppl.ru/ – Видеонаблюдение в Санкт-Петербурге
фотографии на фотоблоге или возможность скачать фотографии бесплатно. фотографии бесплатно. огромное количество уникальных фотографий для просмотра и скачивания – авто, мотоциклы, юмор и аниме. http://cryazone.com/paint/ – рисунки
Webbell – Все для CMS Datalife Engine. Шаблоны, модули, хаки и советы. http://webbell.ru/ – dle ошибки
Музыкальный поисковик http://mp3fuck.ru/. Новинки музыки 2012 скачать бесплатно!
Hair-News Info http://hair-news.info/ Your Hairstyles Source.
HAIR TIPS BLOG. How to have beautiful hair: beauty tips about hair care. http://hair-tips.net/ – Black Hairstyles
HAIR TIPS BLOG. How to have beautiful hair: beauty tips about hair care. http://hair-tips.net/ – Brunette Hair Tips
БАНКИ РОССИИ. http://vse-banki-rossii.ru/ – банковские кредитные карты
стратегия развития малого бизнеса, качественная разработка блок-схем и аудит интернет-магазина. используйте ключевые факторы успеха интернет-магазина. проведем быстрый PEST-анализ по приемлемой стоимости от профи. http://stratplan.ru/ – описание бизнес-процессов
наша фабрика обуви Gassa предлагает профессиональное производство различной обуви и оптовые поставки обуви. обувь. у нас вы всегда можете заказать качественные мокасины, тапочки и сандали по выгодным расценкам. http://gassa.ru/ – мужская обувь