【数据结构重温】Linux内核中的hash和bucket
哈希表（Hashtable）又称为“散置”，Hashtable是会根据索引键的哈希程序代码组织成的索引键（Key）和值（Value）配对的集合。Hashtable 对象是由包含集合中元素的哈希桶（Bucket）所组成的。而Bucket是Hashtable内元素的虚拟子群组，可以让大部分集合中的搜寻和获取工作更容易、更快速。
哈希函数（Hash Function）为根据索引键来返回数值哈希程序代码的算法。索引键（Key）是被存储对象的某些属性值（Value）。当对象加入至 Hashtable时，它存储在与对象哈希程序代码相符的哈希程序代码相关的Bucket中。当在Hashtable内搜寻值时，哈希程序代码会为该值产生，并且会搜寻与该哈希程序代码相关的Bucket。例如，student和teacher会放在不同的Bucket中，而dog和god会放在相同的 Bucket中。所以当索引键是唯一从Hashtable获取元素的性能时表现会较好。Hash的四大优点如下所示。
事先不需要排序。
搜寻速度与数据多少无关。
数字签名的密码技术保密性（Security）高。
可做数据压缩（Data Compression），以节省空间。
读过Linux内核源码的人可能都会发现，其中并没有太多复杂的数据结构，作为基础数据结构的双向链表（list）和基于list实现的hash表占据了绝大部分数据结构。内核为什么会大量使用这两种数据结构呢？围绕这个问题（主要是hash表），我将以自己的理解揣摩一下其意图。
首先，这两种数据结构都十分简单，简单包括理解起来简单和使用起来简单两方面内容。这也意味着代码的可读性和可维护性都比其他复杂的数据结构要好，出现bug的风险也较低。从哲学上来讲，这也符合K.I.S.S.条款。
其次，内核是一个比较讲究性能的软件，为了程序设计和维护的简单性而失掉性能，这究竟是不是算得不偿失呢？我们是不是应该将天平更加偏向于性能？已经记不起是在哪里听说过，很多商业的路由软件都是基于二叉树的数据结构来存储路由项，以求得其路由查找的时间复杂度为log(n)，并且他批评Linux的路由项组织为hash表，致使性能不佳，不适合商业。确实有一定道理，可仔细分析，hash表的性能真的比二叉树差么？二叉树的插入和删除某一项的时间复杂度都为log(n);hash表插入和删除的时间复杂度最好为O(1)，最差为O(n)，如果选取的表项(m)足够多，且hash函数足够好的话，其时间复杂度为O(n/m)（当m<=n时）。当m > n / log(n)的时候，hash表的平均表现就比二叉树要好;且当m>=n时，其时
相关文档：
创建桌面图标
目前将网络应用扩展到桌面是一个趋势，存在着很多解决方案，本文以 Mozilla Prism 为例，类似的方法同样适用于 Google Chrome 。
1. 到 Mozilla Prism 的网站上下载 Prism，点击 Download Now 之后会提示有两种，一种是以 Mozilla Firefox 扩展的方式，适合已经安装有 Firefox 的朋友；一� ......
Linux软件包，常见的格式包括有rpm,deb,tar,gz,tgz,zip,bz2等等。几乎每个linux软件都会提供tar的格式的软件包，因为这种格式的软件包任何版本的linux都支持，所以大家至少要了解tar和rpm的使用方法。至于deb可用alien工具转换成tgz或rpm方式。bz2可用bunzip2解包即可。
一、RPM文件的安装
RPM 是RedHat Package ......
一、Linux内核模块的管理
1、lsmod 列加以挂载的内核模块；
lsmod 是列出目前系统中已加载的模块的名称及大小等；另外我们还可以查看 /proc/modules ，我们一样可以知道系统已经加载的模块；
代码:
[root@localhost beinan]# lsmod
2、modinfo 查看模块信息；
modinfo 可以查看模块� ......
STAT(该行程的状态)
D: 不可用信号中断的睡眠状态
R: 正在执行或处于执行队列中
S: 可以用信号中断的睡眠状态
T: 暂停执行
Z: 僵死状态
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
W: 没有足够的记忆体分页可分配
<: 高优先序的行程
N: 低优先序的行程&nbs ......
在Linux下看电视
时间：2009-12-09 13:37:00 来源：网络 作者：小卢
长期以来，在Linux操作系统下使用电视卡是一件比较麻烦的事，这是因为各家电视卡生产厂商都没有提供官方的Linux驱动，只有Windows下的WDM驱动。
Linux下的电视卡驱动，一直由linux.bytesex.org的Linux爱好者负责开发。该驱动有两 ......
