Hash算法的用途

• 产生全局唯一标识 尽管不可能，不过小范围内可行，下面会讨论。
• 校验和(Checksum) 其实Checksum和Hash还是有区别的，看这里。
• 密码安全 一般主要用来做密码的签名，例如在数据库里存放MD5后的密码。如果要保证密码的安全，防止被彩虹表攻击，可以加盐(Salt)。
• Hash表索引 这个应该最常用的。

Hash算法随用途的不同而不同，例如校验和(Checksum)Hash算法需要尽量高效、快速(如CRC)，而在密码安全是则必须低效、缓慢从而避免被暴力破解(如MD5、SHA-1等)。

理想中的Hash算法的一个共同特点那就是产生的值是随机和唯一的，但根据鸽子窝原理(pigeonhole principle)这是不可能的，但是碰撞发生的概率大体是怎么分别的呢？

生日悖论

这个Hash的碰撞问题其实与生日悖论(Birthday problem)一样：

    如果一个班级上有30个同学，则至少出现两个人同生日的概率是多少？（假设不考虑闰年，一年365天）

归纳一下问题变成：

    假设从集合m中取n个(n > 0, n <= m)，则取出相同的概率是多少？

用高中的组合数学得到公式如下：

因为k/m远远小于1（k为30，m为365），可以用泰勒级数的一级近似表示

最后得到结果：

这样可以算出生日悖论里的概率来：

    30个人中有同生日的概率P(30) = 70%
    70个人中有同生日的概率P(70) = 99% （这个足够让人惊讶了，这就是为什么叫悖论的原因了:)）

概率的分布图：

Hash算法的碰撞概率

假设Hash算法是随机的，根据以前的公式得到碰撞的概率P(m,n)，m代表Hash产生的个数（一般为2^n，MD5为128位，所以为2^128），n为连续Hash的次数，当n值远小于M时用泰勒级数一级近似得到简化的公式：

P(m,n) =

Hash多少次以后碰撞的概率为50%呢？也就是根据概率和m求出n：

N(p, m) =

    16位Hash碰撞概率为50%，则n = 301次
    32位Hash碰撞概率为50%，则n = 77162次
    128位MD5碰撞概率为50%，则n = 21,719,381,355,163,562,492次

参考

http://en.wikipedia.org/wiki/Birthday_paradox

http://www.codinghorror.com/blog/2007/12/hashtables-pigeonholes-and-birthdays.html

http://www.codinghorror.com/blog/2012/04/speed-hashing.html

http://www.skrenta.com/2007/08/md5_tutorial.html

以前我在公司里推广过SVN，几年下来同事们普遍很抵触，在我面前抱怨SVN的各种问题，TortoiseSVN尽管方便了SVN的操作，但是操作错误发生的几率很高，往往是同事在删除、移动、重命名文件夹时，突然来个感叹号，搞的同事都不敢删文件了:)。还有就是那个rename，SVN是直接删除文件再添加的，偌大一个工程下每个都删除再添加一遍，看的我心都寒了。

Git自发布以来，借着Linux之父Linus Torvalds的名声大红大紫，有了像github这样的杰作。Linus还在演讲中公开侮辱SVN是史上最毫无意义的项目，从项目开始就这样了。Git不同于SVN的集中式管理，它是分布式的，代码仓库可以整个克隆到电脑上，也就是说一旦服务器挂了，你还可以提交、查看日志，这是SVN想都不敢想的。Git保持一贯的简洁和效率，这也是Git的设计原则，相比而言SVN一堆.SVN文件夹和龟速更新数据，差距很大啊。

说了这么多，到动手的时候了，从这里下载msysgit(Git for Windows)，安装之后打开Git Bash。因为毕竟Git是Linux的东东，所以命令行操作也是不可避免的，如果习惯了乌龟TortoiseSVN的话可以考虑TortoiseGit，操作基本差不多。

至于学习的教程推荐Pro Git，熟悉Git的命令很有必要。

接下来就是设置Git了，还是那个中文编码问题（参考这里），这是中文用户永远的痛啊!

最后Show一下我在github上的初步成果:波波的github，fork了两个项目：

• kukkaisvoima: 本博客系统源代码，在原项目上扩展了中文和markdown语法支持。
• gvimfullscreen_win32: vim的全屏支持，我优化了一下代码。

以前我在Project Euler上做题时很多都是跟质数有关的，而托斯特尼筛法(Sieve of Eratosthenes)是我感觉最简洁强大的，它的算法复杂度要小于O(n)，典型的空间换时间算法。

按我的理解不同于其他用循环试除查找质数的方法，埃拉托斯特尼筛法不用除法而是用乘法。原理很简单：

1. 假设有张表里面放了数字2到10
2. 因为2的倍数：4、6，8，10都是合数，所以用笔划掉，剩下3、5、7、9，而第一个没有被划掉的是质数，所以3是质数（因为3不是小于3的数的倍数，也就是说不能被整除）。
3. 划去3的倍数：9，剩下5、7，所以5是质数
4. 划去5的倍数：无，剩下7，所以7是质数
5. 划去7的倍数：无，没有剩下数字
6. 查找完毕，质数是(2、3、5、7)

这个操作很像筛沙子，所以筛法因此得名吧，这里有一个在线JavaScript演示版。如果这张表长为N，一般只要划去小于等于N平方根的数的倍数就可以了，因为小于N的数如果为合数一定有一个小于等于N平方根的质数，而既然我们已经划到了N的平方根了，所以剩下的都是质数啦。

具体查找质数的编程步骤：

1. 建立从2到N的表
2. 找到第一个没有划掉的数p，这是个质数。如果p大于N的平方根，跳到步骤5
3. 划掉所有没有划掉的p的倍乘
4. 跳到步骤2
5. 没有被划掉的都是小于等于N的质数

上个Python代码，查找小于等于65536的质数:

# -*- coding:UTF-8 -*-
import math

def main():
    # 质数筛子，小于等于65536的质数
    size = 65536
    limit = int(math.sqrt(size))
    # 多加一个，方便索引从0开始
    sieve = [True] * (size + 1)

    prime = []
    for index in range(2, limit + 1):
        if sieve[index] == True:
            # 第一个没被划掉的是质数
            prime.append(index)

            # 划掉index的倍乘
            for factor in range(index*2, size+1, index):
                sieve[factor] = False

    # 剩下的都是质数
    for index in range(limit + 1, size+1):
        if sieve[index] == True:
            prime.append(index)

    # 显示所以质数
    print prime

if __name__ == "__main__":
    main()

最近我用C++写的程序需要调用一个Python脚本，之前看过这方面资料无非就是调用Python的C API，我还专门研究了一番Python的C++包装库Pycxx，但都无功而返，没办法只能老老实实的用py2exe打包了:)。 上py2exe官网看了会教程，我发现还算简单，马上动手写了个setup.py：
# py2exe convert python script to exe
from distutils.core import setup
import py2exe

setup(
        console=["AutoUpdate.py"],
        data_files=[
            (".", ["C:\Python27\msvcr90.dll", "C:\Python27\Microsoft.VC90.CRT.manifest"])
            ],
        #zipfile="library.zip",
        options={
            "py2exe":{
                "unbuffered":True,
                "optimize":2,
                "compressed":True,
                "bundle_files":2,
                "dist_dir":"..\"
                }
            }
        )
 其中setup函数的options的py2exe的bundle_files参数（很拗口啊）有三个值： 

• 1 = 所有模块都打包进exe，最终生成单独的exe文件(需要设置zipfile=None)
• 2 = 除python27.dll外模块都打包进exe文件
• 3 = 模块都不打包进exe，会生成很多文件，这是默认 如果你有洁癖，不喜欢乱糟糟的文件的话可以考虑把bundle_files设置成1。 还有一个问题是

依赖VC动态库问题，幸好在Python安装目录下有。我现在装的是Python2.7.1，安装在C:Python27下，里面有MSVCR90.DLL(版本号9.0.21022.8)和Microsoft.VC90.CRT.manifest两个文件拷到当前目录就行了。

每次在Vim下用:!执行外部命令都会弹出烦人的控制台命令提示“Hit any key to close this window…”，同时当前的Vim窗口也会挂起提示你请按ENTER或其他命令继续。

:silent大法

一般Vim执行外部命令后会提示你请按ENTER或其他命令继续刷新窗口，如果你想避免刷新就可以用:silent命令，而且:silent命令还可以去掉执行外部程序时的“Hit any key to close this window…”提示。

:silent {command}

需要注意的是执行:silent后如果需要的话可以按CTRL-L或:redraw手动刷新窗口，如果同时执行多个命令需要在每个命令前都写上:silent，如:silent !command1 :silent !command2 …。

用:silent修改之前的Vim Markdown转换：

" Markdown to HTML on Windows 
nmap <leader>md :w<cr>:silent !markdown.py "%">"%.html"<cr>:silent !"%.html"<cr>

:!start（Vim异步执行命令）

尽管前面的:silent大法已经可以不用频繁的按键了，但是还是会有控制台命令提示窗口弹出。有没有什么办法可以不留一点痕迹呢，这就是Vim的异步命令执行。

在Vim下用!:command会同步方式运行外部程序从而阻塞Vim窗口，等待程序运行完成才按任意键返回，而如果用异步方式的话就不会出现这种情况。Vim异步运行命令是：

:!start {command}

如果是在Windows控制台中运行的命令，需要额外加cmd /c ：

:!start cmd /c "command1 param" && command2 

用:start修改之前的Vim Markdown转换：

" Markdown to HTML on Windows
nmap <leader>md :w<cr>:silent !start cmd /c "markdown.py %>%.html" && %.html<cr>

参考

Execute external programs asynchronously under Windows

Avoiding the “Hit ENTER to continue” prompts

前言

这个博客是用基于Python的Kukkaisvoima搭建的，前几天才发现Kukkaisvoima已经更新到14了。从官网下载源码后，我大致看了一下，主要是一些小修改：添加了年和月的目录、修改了时间格式，终于添加了渴望已久的RSS图标;)。

既然更新了博客程序就不得不说写博客了，由于Kukkaisvoima只支持纯HTML的txt文本方式（连文件后缀都要.txt），所以写起来很费劲。话说HTML尽管很直观但也不是容易写的。之前遇到的最大困难是不支持自动换行，我的做法是直接改Kukkaisvoima源码，在每一行最后加<p>分段，凑合着还能用。最近发现很多人都用Markdown写博客，Markdown语法简洁，可以很方便转成HTML，最主要的是有Python支持，看起来很符合我的胃口，所以马上动手把Markdown集成进Kukkaisvoima。

准备

• Markdown的语法说明
• Python Markdown库最新版本为2.1.1

  Linux下安装:

  wget http://pypi.python.org/packages/source/M/Markdown/Markdown-2.x.x.tar.gz
  tar xvzf Markdown-2.x.x.tar.gz
  cd Markdown-2.x.x/
  sudo python setup.py install
  

  命令行用法：

  markdown_py --help
  

• Vim的Markdown语法插件，Markdown文件扩展名为.md/.mkd/.mkdn/.mark*

  由于Kukkaisvoima只支持后缀.txt文件，所以使用语法文件时可以手动修改文件类型时Vim支持Markdown语法，注意txt文件编码是UTF-8，在Vim命令模式输入：

  :set filetype=markdown
  

  在Vim配置文件中加入下面几行可以实时转换并用浏览器查看效果,按md进行转换：

  " markdown to HTML on Linux 
  nmap <leader>md :w<cr>:silent !markdown_py "%">"%.html"<cr>:silent !firefox "%.html"<cr>
  
  " Markdown to HTML on Windows
  nmap <leader>md :w<cr>:silent !markdown.py "%">"%.html"<cr>:silent !"%.html"<cr>
  

修改

在Kukkaisvoima的主文件index.cgi开头添加Markdown的Python库导入：

import markdown

在index.cgi的Entry类析构函数中读取博客文本时进行Markdown解析：

class Entry:
    firstpre = re.compile("<p.*?(</p>|<p>)", re.DOTALL | re.IGNORECASE)
    whitespacere = re.compile("s")
    def __init__(self, fileName, datadir):
        self.fileName = fileName
        self.fullPath = os.path.join(datadir, fileName)

        # Markdown support 
        tempf = open(self.fullPath, 'r')
        self.headline = tempf.readline()
        temptext = tempf.read()
        temptext = temptext.decode(encoding)
        temptext = markdown.markdown(temptext)
        temptext = temptext.encode(encoding)
        self.text = temptext.splitlines(True)

        #self.text = [line for line in self.text if not line.startswith('#')]
        #self.headline = self.text[0]
        #self.text = self.text[1:]
        self.author = defaultauthor
        self.cat = ''
        name, date, categories = fileName[:-4].split('_')
        self.cat = categories.split(',')
        self.date = generateDate(self.fullPath)
        self.comments = getComments(self.fileName)
        self.url = "%s/%s" % (baseurl,
                              quote_plus(self.fileName[:-4]))

由于Markdown的Python库只支持Unicode的输入输出，所以需要在UTF-8和Unicode之间进行转换。

效果

大功告成之后测试一下，用Markdown修改之前写的博文：

Markdown:

**引言：**
>A Wise old computer scienist once said: Make your data structure
>smart and your code dump.
>
>We need SMART Models, THIN Controllers, and DUMB Views.

HTML:

引言：

A Wise old computer scienist once said: Make your data structure
smart and your code dump.

We need SMART Models, THIN Controllers, and DUMB Views.

总体来说效果不错，基本上能满足我写博客的需求了，至于其他的如添加Tag的属性之类的只能用HTML来写了:)。

具体的编程就是简单的穷举法了，因为左右对称，所以有两种解法。直接上个Python代码：

运行结果：