128. 哈希函数

描述

在数据结构中,哈希函数是用来将一个字符串(或任何其他类型)转化为小于哈希表大小且大于等于零的整数。一个好的哈希函数可以尽可能少地产生冲突。一种广泛使用的哈希函数
算法是使用数值33,假设任何字符串都是基于33的一个大整数,比如:

    hashcode("abcd") = (ascii(a) * 333 + ascii(b) * 332 + ascii(c) *33 + 
                        ascii(d)) % HASH_SIZE 
                     = (97* 333 + 98 * 332 + 99 * 33 +100) % HASH_SIZE
                     = 3595978 % HASH_SIZE

其中HASH_SIZE表示哈希表的大小(假设一个哈希表就是一个索引0 ~ HASH_SIZE-1的数组)
给出一个字符串作为key和一个哈希表的大小,返回这个字符串的哈希值

说明

For this problem, you are not necessary to design your own hash algorithm or consider any collision issue, you just need to implement the algorithm as described.

样例

对于key="abcd" 并且 size=100, 返回 78

代码

public class Solution {
    /*
     * @param key: A string you should hash
     * @param HASH_SIZE: An integer
     * @return: An integer
     */
    public int hashCode(char[] key, int HASH_SIZE) {
        // 当数值很大时,如果用 int 会越界
        long ans = 0;
        for (int i = 0; i < key.length; i++) {
            // 注意强制转换的写法
            // ans 值如果大于 HASH_SIZE,用 HASH_SIZE 来取模
            // 这个地方也可以写成 (long)key[i]
            ans = (ans * 33 + (int)(key[i])) % HASH_SIZE;
        }
        return (int)ans;
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 题目 在数据结构中,哈希函数是用来将一个字符串(或任何其他类型)转化为小于哈希表大小且大于等于零的整数。一个好的哈...
    六尺帐篷阅读 374评论 0 1
  • 描述 在数据结构中,哈希函数是用来将一个字符串(或任何其他类型)转化为小于哈希表大小且大于等于零的整数。一个好的哈...
    lyoungzzz阅读 257评论 0 0
  • 在数据结构中,哈希函数是用来将一个字符串(或任何其他类型)转化为小于哈希表大小且大于等于零的整数。一个好的哈希函数...
    DayDayUpppppp阅读 375评论 0 0
  • 版权声明:本文为博主原创文章,未经博主允许不得转载。 难度:容易 要求: 在数据结构中,哈希函数是用来将一个字符串...
    柒黍阅读 236评论 0 0
  • //联系人:石虎QQ: 1224614774昵称:嗡嘛呢叭咪哄 01.用户信息安全================...
    石虎132阅读 751评论 2 13