这是Live555源码阅读的第一部分，包括了时间类，延时队列类，处理程序描述类，哈希表类这四个大类。

本文由乌合之众 lym瞎编，欢迎转载 http://www.cnblogs.com/oloroso/

本文由乌合之众 lym瞎编，欢迎转载 my.oschina.net/oloroso

BasicHashTable的辅助方法

这里介绍的是一些用来对哈希表进行一些基本的哈希操作的函数。

randomIndex(uintptr_t i) const方法

randomIndex(uintptr_t i) const方法是这个BasicHashTable的散列算法。它将各个TableEntry对象的key散列到不同的桶中去，就是获取key对应桶的索引。

下面代码中的注释已经比较清楚了，稍微再解释一下。

我们之前已经说过了，一个桶可能会有多个条目相关联。哈希表的特点就是要快速查找，那么一个key对应到一个桶，然后从桶中查找条目就加快了速度。这个i * 1103515245 就是一个用来产生伪随机数的操作。这个函数在key类型不为字符串的时候会使用到。因为是伪随机数，所以只要i不变，结果就不变。在使用的时候会使用key来替代i。所以只要key相同，会散列到同一个桶中。

fDownShift是用来降档移位的。如果 i=123,那么i * 1103515245的结果是 135732375135 转为二进制就是

1001 1010 0100 0111 1010 1110 0101 1111		这里只看32位，溢出的部分不要了，然后将其左移 fDownShift =28 位

0000 0000 0000 0000 0000 0000 0000 1001		这也一来就只剩下了最后四位有效了，其余的都被清零了。然后&fMask=0x3

0000 0000 0000 0000 0000 0000 0000 0001		因为0x3的二进制形式为 0011（前面28位皆为0），所以相当于就是清零了

											前面的30位，只留下最低两位。之前说过默认的桶数是4个，而两个二进制位

											能表示的是 0、1、2、3四种可能，刚刚好。

如果重建桶，那么fDownShift和fMask的值必须有相应的改变。这个在后面会介绍。这里补充一下，上面所做的二进制表示都是在小端序的情况下的。

//随机化索引，其实并非随机。产生一个与i有关的随机值，这是单向不可逆的

	unsigned randomIndex(uintptr_t i) const {

		//1103515245这个数很有意思，rand函数线性同余算法中用来溢出的

		//这个函数的作用就是返回一个随机值，因为默认fMask(0x3)，也就是只保留两位

		//为什么只要保留2位，也就是0 1 2 3 这四种结果咯，因为桶默认只有四个

		// fDownShift用来移位，其默认是28，每次调整哈希表大小的时候会减2

		return (unsigned)(((i * 1103515245) >> fDownShift) & fMask);

	}

---

hashIndexFromKey(char const* key) const方法

hashIndexFromKey方法将一个key值散列得到一个index索引值。

这里不多解释了，代码很明白。根据key的类型，进行不同方式的散列，得到index索引返回。这个方法是用于实现后面将介绍的多个方法的关键。

unsigned BasicHashTable::hashIndexFromKey(char const* key) const {

  unsigned result = 0;

  //如果键的类型是字符串

  if (fKeyType == STRING_HASH_KEYS) {

    while (1) {

      char c = *key++;	//从key指向字符串一个一个取字符

      if (c == 0) break;

	  //转换为数字型的索引

      result += (result<<3) + (unsigned)c;

    }

    result &= fMask;	//掩码留位操作

  } else if (fKeyType == ONE_WORD_HASH_KEYS) {

    result = randomIndex((uintptr_t)key);

  } else {

    unsigned* k = (unsigned*)key;

    uintptr_t sum = 0;

    for (int i = 0; i < fKeyType; ++i) {

      sum += k[i];

    }

    result = randomIndex(sum);

  }

  return result;

}

---

rebuild重新建表方法

重新建表的时候，会动态申请一个是原本桶数组大小四倍的新桶数组。然后将原哈希表中的条目重新散列到新表，因为新表的大小与原本的不同了，fDownShift和fMask必须改变来适应新的桶数组，因此必须重新散列

-。

每一次重建表的时候，因为桶的个数是原来的四倍，所以散列的时候保留的位数必须得到相应的改变。我们可以计算得到，每次保留的位数必须是在原来基础上增加两位，因为2位可以表示4种可能，就是总的表示范围扩大了4倍。所以fDownShift每次减去2，而fMask每次右移两位然后按位或0x3操作。

这是一个private权限的方法，在Add方法中调用。

void BasicHashTable::rebuild() {

  // Remember the existing table size:

  unsigned oldSize = fNumBuckets;

  TableEntry** oldBuckets = fBuckets;

  // Create the new sized table:

  fNumBuckets *= 4;

  fBuckets = new TableEntry*[fNumBuckets];

  for (unsigned i = 0; i < fNumBuckets; ++i) {

    fBuckets[i] = NULL;

  }

  fRebuildSize *= 4;

  fDownShift -= 2;

  fMask = (fMask<<2)|0x3;

  // Rehash the existing entries into the new table:

  // 重新散列，把现有的条目加入到新表

  for (TableEntry** oldChainPtr = oldBuckets; oldSize > 0;

       --oldSize, ++oldChainPtr) {

    for (TableEntry* hPtr = *oldChainPtr; hPtr != NULL;

	 hPtr = *oldChainPtr) {

      *oldChainPtr = hPtr->fNext;

      unsigned index = hashIndexFromKey(hPtr->key);

      hPtr->fNext = fBuckets[index];

      fBuckets[index] = hPtr;

    }

  }

  // Free the old bucket array, if it was dynamically allocated:

  // 释放旧的桶数组，如果它是动态申请的

  if (oldBuckets != fStaticBuckets) delete[] oldBuckets;

}

---

deleteKey和deleteEntry方法

deleteKey方法将一个条目的key删除。这个方法用于实现deleteEntry方法。

void BasicHashTable::deleteKey(TableEntry* entry) {

  // The way we delete the key depends upon its type:

  if (fKeyType == ONE_WORD_HASH_KEYS) {

    entry->key = NULL;

  } else {

    delete[] (char*)entry->key;

    entry->key = NULL;

  }

}

deleteEntry用于从哈希表中删除一个条目，并且这个条目会被回收。这里有一个参数index，这个参数指明了这个entry从哪一个桶中查找。这个方法的权限是private的，所以这里不用担心index传错了的情况，这个在调用的时候会根据条目entry的key来确定的。如果没有找到，那也没有关系，本来就是要从哈希表中移除的，没有就等于是已经移除了。

void BasicHashTable::deleteEntry(unsigned index, TableEntry* entry) {

  TableEntry** ep = &fBuckets[index];

  Boolean foundIt = False;

  while (*ep != NULL) {

    if (*ep == entry) {

      foundIt = True;

      *ep = entry->fNext;

      break;

    }

ep = &((*ep)->fNext);		//找到了就从hashTable中移除

}

  if (!foundIt) { // shouldn't happen

#ifdef DEBUG

    fprintf(stderr, "BasicHashTable[%p]::deleteEntry(%d,%p): internal error - not found (first entry %p", this, index, entry, fBuckets[index]);

    if (fBuckets[index] != NULL) fprintf(stderr, ", next entry %p", fBuckets[index]->fNext);

fprintf(stderr, ")\n");

#endif

}

  --fNumEntries;

  deleteKey(entry);

  delete entry;

}

---

assignKey方法

assignKey方法用于给条目*entry的key成员分配一个与参数key 等大小的空间，并拷贝其指向的内容。简单的说就是使用参数key给条目entry创建key。这个方法用与实现insertNewEntry方法。函数strDup在strDup.cpp中实现，其作用是在堆上分配一个刚好可以保存key指向的字符串的空间，然后拷贝key指向字符串内容到新的空间，返回新空间地址。

void BasicHashTable::assignKey(TableEntry* entry, char const* key) {

  // The way we assign the key depends upon its type:

  if (fKeyType == STRING_HASH_KEYS) {

    entry->key = strDup(key);	//给条目的key成员分配空间

  } else if (fKeyType == ONE_WORD_HASH_KEYS) {

    entry->key = key;

  } else if (fKeyType > 0) {

    unsigned* keyFrom = (unsigned*)key;

    unsigned* keyTo = new unsigned[fKeyType];

    for (int i = 0; i < fKeyType; ++i) keyTo[i] = keyFrom[i];

    entry->key = (char const*)keyTo;

  }

}

---

insertNewEntry方法(插入新条目)

insertNewEntry方法用于使用key创建一个新条目，然后将这个新条目插入到index桶的位置。这是链表的头插法。这也是private权限的，在调用的时候index会根据key来生成。注意的是，目前这个条目的value未赋值。

BasicHashTable::TableEntry* BasicHashTable

::insertNewEntry(unsigned index, char const* key) {

  TableEntry* entry = new TableEntry();

  entry->fNext = fBuckets[index];

  fBuckets[index] = entry;

  ++fNumEntries;

  assignKey(entry, key);

  return entry;

}

---

keyMatches方法(键比较)

keyMatches方法用于比较两个key是否一致。这个方法用于实现lookupKey方法。

Boolean BasicHashTable

::keyMatches(char const* key1, char const* key2) const {

  // The way we check the keys for a match depends upon their type:

  if (fKeyType == STRING_HASH_KEYS) {

    return (strcmp(key1, key2) == 0);

  } else if (fKeyType == ONE_WORD_HASH_KEYS) {

    return (key1 == key2);

  } else {

    unsigned* k1 = (unsigned*)key1;

    unsigned* k2 = (unsigned*)key2;

    for (int i = 0; i < fKeyType; ++i) {

      if (k1[i] != k2[i]) return False; // keys differ

    }

    return True;

  }

}

---

lookupKey方法(查找条目)

lookupKey使用key来确定index和要查找的条目。注意参数index是一个引用，是作为传出参数的。如果查找失败，会返回NULL。

与前面几个一样，这也是private权限的。这几个方法主要用于实现BasicHashTable从类HashTable中继承的几个虚函数。即对哈希表的增删查改。

BasicHashTable::TableEntry* BasicHashTable

::lookupKey(char const* key, unsigned& index) const {

  TableEntry* entry;

  index = hashIndexFromKey(key);	//确定在那个桶里

  //因为一个桶代表一个链表，需要判断找到的条目的key是否对得上

  for (entry = fBuckets[index]; entry != NULL; entry = entry->fNext) {

if (keyMatches(key, entry->key)) break;

}

  return entry;

}