月度归档:2016年06月

词典

词典(dictionary)这种数据结构在编程语言中很常见,比如Java中的HashMap与Hashtable、Python中的字典等等,一个键值对可以称为一个词条,即entry = (key, value),而映射(map)就是词条的集合,但其中各词条(的关键码)互异,词典与映射基本相同,但允许词条的(关键码)雷同,进一步,关键码之间可以定义全序关系的词典称为有序词典(sorted dictionary),映射和词典都是动态的,统称符号表(symbol table)。实现词典的重要技术便是散列(hash),与其说散列是一种技术,不如说散列是一种思想,它重点解决的问题是数据结构在空间效率上的提高,而依照散列思想所实现的数据结构的访问方式不妨称为寻值访问(call-by-value),这种方式更为自然,适用范围也更广泛。 继续阅读