Generic Perfect Hash Generator
------------------------------
*Ilan Schnell, 2008*
perfect_hash.py provides a perfect hash generator which is not language
specific. That is, the generator can output a perfect hash function for
a given set of keys in any programming language, this is achieved by
filling a given code template.
### Acknowledgments:
This code is derived from A. M. Kuchling's
[Perfect Minimal Hash Generator](http://www.amk.ca/python/code/perfect-hash).
### Introduction:
A perfect hash function of a certain set S of keys is a hash function
which maps all keys in S to different numbers.
That means that for the set S,
the hash function is collision-free, or perfect.
Further, a perfect hash function is called minimal when it maps n keys
to n *consecutive* integers, usually in the range from 0 to n-1.
After coming across A. M. Kuchling's Perfect Minimal Hash Generator,
I decided to write a general tool for generating perfect hashes.
It is general in the sense that it can produce perfect hash functions
for almost any programming language.
A given code template is filled with parameters,
such that the output is code which implements the hash function.
The algorithm the program uses is described in the paper
["Optimal algorithms for minimal perfect hashing"]
(http://citeseer.ist.psu.edu/122364.html),
Z. J. Czech, G. Havas and B.S. Majewski.
I tried to illustrate the algorithm and explain how it works on
[this page](http://ilan.schnell-web.net/prog/perfect-hash/algo.html).
### Usage:
Given a set of keys which are ordinary character string,
the program returns a minimal perfect hash function.
This hash function is returned in the form of Python code by default.
Suppose we have a file with keys:
# 'animals.txt'
Elephant
Horse
Camel
Python
Dog
Cat
The exact way this file is parsed can be specified using command line
options, for example it is possible to only read one column from a file
which contains different items in each row.
The program is invoked like this:
# =======================================================================
# ================= Python code for perfect hash function ===============
# =======================================================================
G = [0, 0, 4, 1, 0, 3, 8, 1, 6]
S1 = [5, 0, 0, 6, 1, 0, 4, 7]
S2 = [7, 3, 6, 7, 8, 5, 7, 6]
def hash_f(key, T):
return sum(T[i % 8] * ord(c) for i, c in enumerate(str(key))) % 9
def perfect_hash(key):
return (G[hash_f(key, S1)] + G[hash_f(key, S2)]) % 9
# ============================ Sanity check =============================
K = ["Elephant", "Horse", "Camel", "Python", "Dog", "Cat"]
H = [0, 1, 2, 3, 4, 5]
assert len(K) == len(H) == 6
for k, h in zip(K, H):
assert perfect_hash(k) == h
The way the program works is by filling a code template with the calculated
parameters. The program can take such a template in form of a file and
fill in the calculated parameters, this allows the generation of perfect
hash function in any programming language. The hash function is kept quite
simple and does not require machine or language specific byte level operations
which might be hard to implement in the target language.
The following parameters are available in the template, and will expand to:
string | expands to
--------+--------------------------------
$NS | the length of S1 and S2
$S1 | array of integers S1
$S2 | array of integers S2
$NG | length of array G
$G | array of integers G
$NK | the number of keys, i.e. length of array K and H
$K | array with the quoted keys
$H | array of integer hash values
$$ | $ (a literal dollar sign)
A literal '$' is escaped as '$$'. Since the syntax for arrays is not the
same in all programming languages, some specifics can be adjusted using
command line options.
The section of the built-in template which creates the actual hash function
is:
G = [$G]
S1 = [$S1]
S2 = [$S2]
def hash_f(key, T):
return sum(T[i % $NS] * ord(c) for i, c in enumerate(str(key))) % $NG
def perfect_hash(key):
return (G[hash_f(key, S1)] + G[hash_f(key, S2)]) % $NG
Using code templates, makes this program very flexible. The package comes
with several complete examples for C and C++. There are many choices one
faces when implementing a static hash table: do the parameter lists go into
a separate header file, should the API for the table only contain the hash
values, but not the objects being mapped, and so on.
All these various choices are possible because of the template is simply
filled with the parameters, no matter what else is inside the template.
Another possible use the program is as a python module. The functions and
classes in 'perfect_hash.py' are documented and have clean interfaces.
The folder 'example-Python' has examples which shows how the module
can be used directly in this way.
### Requirement:
Python 2.5
没有合适的资源?快使用搜索试试~ 我知道了~
RTGUI-master.zip
共325个文件
c:152个
h:85个
sconscript:24个
5星 · 超过95%的资源 需积分: 20 49 下载量 115 浏览量
2014-07-11
15:30:58
上传
评论 2
收藏 1.02MB ZIP 举报
温馨提示
RT_Thread从1.10版开始不再包含RTGUI源码,而是将RTGUI拉出来单独开发,单独发布。
资源推荐
资源详情
资源评论
收起资源包目录
RTGUI-master.zip (325个子文件)
hz16font.c 1.6MB
hz12font.c 1.17MB
region.c 70KB
asc12font.c 70KB
dc_blend.c 65KB
edit.c 60KB
dc.c 43KB
blit.c 34KB
topwin.c 32KB
image_bmp.c 30KB
dc_rotozoom.c 28KB
rtgui_theme.c 27KB
image_jpg.c 27KB
asc16font.c 26KB
filelist_view.c 25KB
dc_trans.c 24KB
textbox.c 24KB
window.c 23KB
list_view.c 22KB
notebook.c 22KB
widget.c 20KB
mouse.c 20KB
rtgui_system.c 20KB
scrollbar.c 19KB
image_png.c 18KB
filedialog.c 17KB
image_xpm.c 16KB
dc_buffer.c 15KB
calibration.c 15KB
listctrl.c 14KB
listbox.c 13KB
server.c 12KB
rtgui_mv_model.c 12KB
image_container.c 12KB
rtgui_xml.c 11KB
rtgui_app.c 11KB
container.c 10KB
dc_client.c 10KB
demo_view_window.c 9KB
textview.c 9KB
button.c 9KB
menu.c 9KB
demo_listview_icon.c 8KB
filerw.c 8KB
image.c 8KB
box.c 8KB
radiobox.c 8KB
combobox.c 8KB
image_hdc.c 8KB
plot.c 8KB
slider.c 8KB
messagedialog.c 8KB
dc_hw.c 7KB
digfont.c 7KB
demo_view_bmp.c 7KB
apps_list.c 7KB
demo_view_listctrl.c 7KB
font_hz_file.c 7KB
driver.c 7KB
font_freetype.c 7KB
picture.c 6KB
rtgui_object.c 6KB
demo_view_dc.c 6KB
font_bmp.c 6KB
framebuffer_driver.c 6KB
font_fnt.c 6KB
demo_view_edit.c 6KB
iconbox.c 5KB
matrix.c 5KB
animation.c 5KB
win1_ui.c 5KB
pixel_driver.c 5KB
font_hz_bmp.c 5KB
demo_view_listbox.c 5KB
demo_view_buffer_animation.c 5KB
application.c 5KB
demo_view_instrument_panel.c 4KB
digtube.c 4KB
swin_focus.c 4KB
animation_engines.c 4KB
demo_view.c 4KB
groupbox.c 4KB
title.c 4KB
demo_view_benchmark.c 4KB
checkbox.c 4KB
appmgr.c 4KB
font.c 4KB
demo_view_image.c 4KB
statusbar.c 4KB
application.c 4KB
demo_view_animation.c 4KB
block_panel.c 4KB
demo_view_textbox.c 4KB
demo_application.c 3KB
application.c 3KB
demo_view_label.c 3KB
gesture.c 3KB
application.c 3KB
demo_listview.c 3KB
label.c 3KB
共 325 条
- 1
- 2
- 3
- 4
资源评论
- swcy2252016-09-10东西很好用。谢谢
- snpk1112016-10-14谢谢分享,正在学习
- 啊路YY2016-01-16东西很好用。谢谢
- 逸水天2019-01-20很好的东西,不过后来从GitHub上可以下载到,名称不叫RTGUI了
syz1993
- 粉丝: 0
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 基于51单片机的自动浇花设计论文
- 客服机器人需要的数据集,包括order、ware、user,测试集和开发集
- 用0到9生成十位数的所有排列组合(java代码).docx
- 模仿魔慢相机的人脸监测选择ios组件
- STM32F103C8T6模拟IIC控制4针0.96寸OLED显示屏已测
- Chromeextent_paly.zip
- 【2023年全国职业技能大赛“信息安全与评估”赛项】任务4-Linux内存取证WP+靶场环境
- 基于51单片机数字电压表的设计(PCB+原理图+仿真+论文+代码)
- open62541在window10 VS2019编译完成的源码
- 新闻文章自动新闻采集系统-webapps.rar
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功