用什么概念来发展字典 [英] what concept is used to develop dictionary

问题描述

嗨朋友

我想开发一本需要花费固定时间来搜索每个长词含义的字典..

请给我解决方案..

hi friends

i want to develop a dictionary that take a constant time to search meaning of every length words..

plz send me solution..

推荐答案

请参见

我对性能的理解一般用途的哈希表(词典):您无法获得恒定的访问时间.
一个简单的计数器示例:如果很不幸，所有键都映射到相同的索引"位置，则必须对所有条目进行冲突处理.

如果您的哈希表是约束，例如计算机语言的关键字列表，您可以定制您的哈希算法(关键字计算和哈希大小)，以确保获得第一击或失败.

在很久以前，我在某些Verilog编译器开发中(使用C ++)进行了该练习.我有一组关键字，关键算法是通过简单的操作将前8个左右的字符弄乱成一个整数.
使用perl脚本时，我在开发时通过蛮力一次计算了哈希表的大小，以使每个键模哈希表大小都给出了唯一的索引，并且该表大小在可接受的大小范围内.

有了这个键，您就没有第一个匹配项，或者没有匹配项，并且必须对字符串进行比较.足够接近几乎恒定的访问时间(最坏的情况:最长的单词进行比较，最后一个字符不同于longes关键字-可以忽略).

干杯

安迪

My understanding of the performance of general-purpose hash-tables (dictionaries): you can''t get constant access time.
A simple counter example: If you are unfortunate enough that all keys map to the same "index" location, you have to do collision handling all entries.

If your hash table is contraint, e.g. a key word list for a computer language, you can tailor your hash algoritm (key calculation and hash size) so that you have a guaranted first hit or a failure.

I did that exercise once in the distant past in some Verilog compiler development (in C++). I had a set of key words, the key algoritm was such that the first 8 characters or so were mangled by simple operations into an integer.
With a perl script I calculated a hash table size once at development time by brute force such that each key modulo hash-table-size gave a unique index, and the table-size was in the accepted size range.

With that you had a first hit or none, and with the hit, the string had to be compared. Close enough to almost constant access time (worst case time: longest word to compare, where the last character differs to the longes keyword - neglectable).

Cheers

Andi

这篇关于用什么概念来发展字典的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！