`
美丽的小岛
  • 浏览: 309301 次
  • 性别: Icon_minigender_1
  • 来自: 大连
社区版块
存档分类
最新评论

一些hash函数实现<转>

 
阅读更多

 

/**
* Hash算法大全<br>
* 推荐使用FNV1算法
* @algorithm None
* @author Goodzzp 2006-11-20
* @lastEdit Goodzzp 2006-11-20 
* @editDetail Create
*/
public class HashAlgorithms
{
/**
* 加法hash
* @param key 字符串
* @param prime 一个质数
* @return hash结果
*/
public static int additiveHash(String key, int prime)
{
   int hash, i;
   for (hash = key.length(), i = 0; i < key.length(); i++)
    hash += key.charAt(i);
   return (hash % prime);
}

/**
* 旋转hash
* @param key 输入字符串
* @param prime 质数
* @return hash值
*/
public static int rotatingHash(String key, int prime)
{
   int hash, i;
   for (hash=key.length(), i=0; i<key.length(); ++i)
     hash = (hash<<4)^(hash>>28)^key.charAt(i);
   return (hash % prime);
//   return (hash ^ (hash>>10) ^ (hash>>20));
}

// 替代:
// 使用:hash = (hash ^ (hash>>10) ^ (hash>>20)) & mask;
// 替代:hash %= prime;


/**
* MASK值,随便找一个值,最好是质数
*/
static int M_MASK = 0x8765fed1;
/**
* 一次一个hash
* @param key 输入字符串
* @return 输出hash值
*/
public static int oneByOneHash(String key)
{
   int   hash, i;
   for (hash=0, i=0; i<key.length(); ++i)
   {
     hash += key.charAt(i);
     hash += (hash << 10);
     hash ^= (hash >> 6);
   }
   hash += (hash << 3);
   hash ^= (hash >> 11);
   hash += (hash << 15);
//   return (hash & M_MASK);
   return hash;
}

/**
* Bernstein's hash
* @param key 输入字节数组
* @param level 初始hash常量
* @return 结果hash
*/
public static int bernstein(String key)
{
   int hash = 0;
   int i;
   for (i=0; i<key.length(); ++i) hash = 33*hash + key.charAt(i);
   return hash;
}

//
//// Pearson's Hash
// char pearson(char[]key, ub4 len, char tab[256])
// {
//   char hash;
//   ub4 i;
//   for (hash=len, i=0; i<len; ++i) 
//     hash=tab[hash^key[i]];
//   return (hash);
// }

//// CRC Hashing,计算crc,具体代码见其他
// ub4 crc(char *key, ub4 len, ub4 mask, ub4 tab[256])
// {
//   ub4 hash, i;
//   for (hash=len, i=0; i<len; ++i)
//     hash = (hash >> 8) ^ tab[(hash & 0xff) ^ key[i]];
//   return (hash & mask);
// }

/**
* Universal Hashing
*/
public static int universal(char[]key, int mask, int[] tab)
{
   int hash = key.length, i, len = key.length;
   for (i=0; i<(len<<3); i+=8)
   {
     char k = key[i>>3];
     if ((k&0x01) == 0) hash ^= tab[i+0];
     if ((k&0x02) == 0) hash ^= tab[i+1];
     if ((k&0x04) == 0) hash ^= tab[i+2];
     if ((k&0x08) == 0) hash ^= tab[i+3];
     if ((k&0x10) == 0) hash ^= tab[i+4];
     if ((k&0x20) == 0) hash ^= tab[i+5];
     if ((k&0x40) == 0) hash ^= tab[i+6];
     if ((k&0x80) == 0) hash ^= tab[i+7];
   }
   return (hash & mask);
}

/**
* Zobrist Hashing
*/ 
public static int zobrist( char[] key,int mask, int[][] tab)
{
   int hash, i;
   for (hash=key.length, i=0; i<key.length; ++i)
     hash ^= tab[i][key[i]];
   return (hash & mask);
}

// LOOKUP3 
// 见Bob Jenkins(3).c文件

// 32位FNV算法
static int M_SHIFT = 0;
/**
* 32位的FNV算法
* @param data 数组
* @return int值
*/
    public static int FNVHash(byte[] data)
    {
        int hash = (int)2166136261L;
        for(byte b : data)
            hash = (hash * 16777619) ^ b;
        if (M_SHIFT == 0)
            return hash;
        return (hash ^ (hash >> M_SHIFT)) & M_MASK;
    }
    /**
     * 改进的32位FNV算法1
     * @param data 数组
     * @return int值
     */
    public static int FNVHash1(byte[] data)
    {
        final int p = 16777619;
        int hash = (int)2166136261L;
        for(byte b:data)
            hash = (hash ^ b) * p;
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;
        return hash;
    }
    /**
     * 改进的32位FNV算法1
     * @param data 字符串
     * @return int值
     */
    public static int FNVHash1(String data)
    {
        final int p = 16777619;
        int hash = (int)2166136261L;
        for(int i=0;i<data.length();i++)
            hash = (hash ^ data.charAt(i)) * p;
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;
        return hash;
    }

    /**
     * Thomas Wang的算法,整数hash
     */ 
    public static int intHash(int key)
    {
      key += ~(key << 15);
      key ^= (key >>> 10);
      key += (key << 3);
      key ^= (key >>> 6);
      key += ~(key << 11);
      key ^= (key >>> 16);
      return key;
    }
    /**
     * RS算法hash
     * @param str 字符串
     */
    public static int RSHash(String str)
    {
        int b    = 378551;
        int a    = 63689;
        int hash = 0;

       for(int i = 0; i < str.length(); i++)
       {
          hash = hash * a + str.charAt(i);
          a    = a * b;
       }

       return (hash & 0x7FFFFFFF);
    }
    /* End Of RS Hash Function */

    /**
     * JS算法
     */
    public static int JSHash(String str)
    {
       int hash = 1315423911;

       for(int i = 0; i < str.length(); i++)
       {
          hash ^= ((hash << 5) + str.charAt(i) + (hash >> 2));
       }

       return (hash & 0x7FFFFFFF);
    }
    /* End Of JS Hash Function */

    /**
     * PJW算法
     */
    public static int PJWHash(String str)
    {
        int BitsInUnsignedInt = 32;
        int ThreeQuarters     = (BitsInUnsignedInt * 3) / 4;
        int OneEighth         = BitsInUnsignedInt / 8;
        int HighBits          = 0xFFFFFFFF << (BitsInUnsignedInt - OneEighth);
        int hash              = 0;
        int test              = 0;

       for(int i = 0; i < str.length();i++)
       {
          hash = (hash << OneEighth) + str.charAt(i);

          if((test = hash & HighBits) != 0)
          {
             hash = (( hash ^ (test >> ThreeQuarters)) & (~HighBits));
          }
       }

       return (hash & 0x7FFFFFFF);
    }
    /* End Of P. J. Weinberger Hash Function */

    /**
     * ELF算法
     */
    public static int ELFHash(String str)
    {
        int hash = 0;
        int x    = 0;

       for(int i = 0; i < str.length(); i++)
       {
          hash = (hash << 4) + str.charAt(i);
          if((x = (int)(hash & 0xF0000000L)) != 0)
          {
             hash ^= (x >> 24);
             hash &= ~x;
          }
       }

       return (hash & 0x7FFFFFFF);
    }
    /* End Of ELF Hash Function */

    /**
     * BKDR算法
     */
    public static int BKDRHash(String str)
    {
        int seed = 131; // 31 131 1313 13131 131313 etc..
        int hash = 0;

       for(int i = 0; i < str.length(); i++)
       {
          hash = (hash * seed) + str.charAt(i);
       }

       return (hash & 0x7FFFFFFF);
    }
    /* End Of BKDR Hash Function */

    /**
     * SDBM算法
     */
    public static int SDBMHash(String str)
    {
        int hash = 0;

       for(int i = 0; i < str.length(); i++)
       {
          hash = str.charAt(i) + (hash << 6) + (hash << 16) - hash;
       }

       return (hash & 0x7FFFFFFF);
    }
    /* End Of SDBM Hash Function */

    /**
     * DJB算法
     */
    public static int DJBHash(String str)
    {
       int hash = 5381;

       for(int i = 0; i < str.length(); i++)
       {
          hash = ((hash << 5) + hash) + str.charAt(i);
       }

       return (hash & 0x7FFFFFFF);
    }
    /* End Of DJB Hash Function */

    /**
     * DEK算法
     */
    public static int DEKHash(String str)
    {
        int hash = str.length();

       for(int i = 0; i < str.length(); i++)
       {
          hash = ((hash << 5) ^ (hash >> 27)) ^ str.charAt(i);
       }

       return (hash & 0x7FFFFFFF);
    }
    /* End Of DEK Hash Function */

    /**
     * AP算法
     */
    public static int APHash(String str)
    {
        int hash = 0;

       for(int i = 0; i < str.length(); i++)
       {
          hash ^= ((i & 1) == 0) ? ( (hash << 7) ^ str.charAt(i) ^ (hash >> 3)) :
                                   (~((hash << 11) ^ str.charAt(i) ^ (hash >> 5)));
       }

//       return (hash & 0x7FFFFFFF);
       return hash;
    }
    /* End Of AP Hash Function */
    
    /**
     * JAVA自己带的算法
     */
    public static int java(String str)
{
   int h = 0;
   int off = 0;
   int len = str.length();
   for (int i = 0; i < len; i++)
   {
    h = 31 * h + str.charAt(off++);
   }
   return h;
}
    
    /**
     * 混合hash算法,输出64位的值
     */
    public static long mixHash(String str)
    {
    long hash = str.hashCode();
    hash <<= 32;
    hash |= FNVHash1(str);
    return hash;
    }
}
 

 

来源:

 

http://hi.baidu.com/algorithms/blog/item/79caabee879ece2a2cf53440.html

分享到:
评论

相关推荐

    AJAX 源码范例

    原书附带光盘文件&lt;br&gt;第2章&lt;br&gt; 02/ 基于Ajax的留言板示例&lt;br&gt;第3章&lt;br&gt; 03/3.1.3.html JavaScript在Ajax中的作用范例&lt;br&gt; 03/3.4.6.html 加入注释,实现九九乘法表&lt;br&gt; 03/3.4.11.html 使用逻辑表达式...

    Url消重算法(BloomFilter)

    本程序主要是BloomFilter算法的简化实现&lt;br&gt;因为C#非安全代码无法直接分配内存块,使用了int型数组代替,暂时为了简单没有使用位运算,比位运算消耗内存多16倍。&lt;br&gt;算法原理:&lt;br&gt;其首先申请一块大内存,并把内存中...

    murmurhash.c:MurmurHash3通用hash bashed查找函数实现

    MurmurHash3通用hash bashed查找函数实现 关于 是一种非加密哈希函数,适用于一般的基于哈希的查找。 此实现实现了 MurmurHash 的第 3 版。 安装 : $ clib install jwerle/murmurhash.c 来源: $ git clone git@...

    密码学hash函数关于hash函数的ppt

    - **消息认证码(MAC)**是使用带密钥的Hash函数实现的,它结合了Hash函数的安全特性和密钥的安全性,以确保只有合法接收方才能验证消息的完整性。 2. **数字签名** - 在数字签名过程中,首先使用密码学Hash函数...

    C语言头文件大全1.pdf

    - `&lt;hash_map&gt;`、`&lt;hash_set&gt;`、`&lt;slist&gt;`:这些是基于哈希表实现的映射、集合和单向链表,尽管不在C++标准中,但是是常见的非标准扩展。 文档中还提到,C++标准库由51个必需的头文件组成,且该实现还额外包含了三...

    uthash开源的hash函数实现

    UTHASH 是一个开源的 C 语言库,提供了一种简单且高效的哈希表实现,用于在 C 代码中快速查找和管理数据结构。这个库的主要功能是提供一个宏定义的集合,可以方便地将结构体转化为哈希表,进而进行添加、删除、查找...

    Hash函数研究综述

    ### Hash函数研究综述 #### 引言 Hash函数作为一种重要的密码学组件,在现代信息安全领域扮演着关键角色。它可以用于数字签名方案、验证信息来源的真实性和完整性等方面,并且能够将任意长度的消息压缩到固定长度...

    MD5计算检验工具 x64

    &lt;br&gt;&lt;br&gt; Message-Digest泛指字节串(Message)的Hash变换,就是把一个任意长度的字节串变换成一定长的大整数。请注意我使用了“字节串”而不是“字符串”这个词,是因为这种变换只与字节的值有关,与字符集或编码...

    MD5计算检验工具 x32

    &lt;br&gt;&lt;br&gt; Message-Digest泛指字节串(Message)的Hash变换,就是把一个任意长度的字节串变换成一定长的大整数。请注意我使用了“字节串”而不是“字符串”这个词,是因为这种变换只与字节的值有关,与字符集或编码...

    Hash函数MD5与SHA-1算法实现

    MD5(Message-Digest Algorithm 5)和SHA-1(Secure Hash Algorithm 1)是两种广泛使用的哈希函数,它们在信息安全领域扮演着至关重要的角色。哈希函数是一种将任意长度的数据转换为固定长度输出的函数,这个输出...

    数据结构各种结构的stl实现

    散列(Hash)在STL中通过`&lt;unordered_set&gt;`和`&lt;unordered_map&gt;`实现。它们提供快速的查找操作,基于哈希函数。例如,创建一个存储整数的无序集合: ```cpp #include &lt;unordered_set&gt; std::unordered_set&lt;int&gt; int...

    20多个常用的Hash算法C++ 实现

    Hash函数集合,包含主流的hash函数: nginx_hash算法,OpenSSL_hash算法,RSHash,JSHash,PJWHash,ELFHash,BKDRHash,DJBHash,DEKHash,APHash等等!

    js菜鸟笔记之框架高度自适应_ekom.cn

    接下来,为了让`&lt;iframe&gt;`在内容加载完成后能够自动调整高度,可以在`&lt;iframe&gt;`标签上添加`onload`事件,该事件会在`&lt;iframe&gt;`的内容加载完毕后触发,从而执行相应的函数来调整`&lt;iframe&gt;`的高度。 ```html &lt;iframe ...

    几种常用查找算法的比较

    Link&lt;T&gt; *Find_hash(T key, int &icmp, int ntype = 0) { icmp = 0; if (first == 0) { icmp++; if (ntype) return first = new Link&lt;T&gt;(key); else return NULL; } else { Link&lt;T&gt; *ptr = first, *p; ...

    mycat分片规则

    &lt;property name="mapFile"&gt;partition-hash-int.txt&lt;/property&gt; &lt;property name="type"&gt;0&lt;/property&gt; &lt;property name="defaultNode"&gt;0&lt;/property&gt; &lt;/function&gt; ``` 其中,`columns`指定了分片的表字段,`...

    一些使用频率较高的非常实用的PHP函数

    $html .= "&lt;/head&gt;&lt;body&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;"; $html .= "&lt;table cellspacing='0' cellpadding='0' border='1' width='450' align='center'&gt;"; $html .= "&lt;tr&gt;&lt;td bgcolor='#ffffff'&gt;"; $html .= "&lt;table border='...

    hash函数 实例

    根据给定的文件信息,我们可以总结出以下关于 Hash 函数在 C 语言中的实现与应用的知识点: ### 1. Hash 函数的概念 哈希函数(Hash Function)是一种将任意长度的消息映射到固定长度的消息摘要的一种算法。这种...

    帝国CMS-PHP

    &lt;/p&gt;&lt;p&gt;“来源HASH验证”功能升级,防护更强。&lt;/p&gt;&lt;p&gt;来源地址新增严格模式验证,更严谨,防护外部提交更严格。&lt;/p&gt;&lt;p&gt;TAGS功能升级,更完善。&lt;/p&gt;&lt;p&gt;各系统模型新增记录信息审核人功能,对查看责任人和绩效考核更...

    HASH函数实验指导

    **正文** 在信息技术领域,哈希(Hash)函数与数字签名是两个至关重要的概念,它们在...在实验四的“Hash函数”文档中,会详细阐述这些理论知识,并可能包含具体的操作步骤和示例,以帮助学生加深理解并实践这些概念。

Global site tag (gtag.js) - Google Analytics