LintCode 哈希函数题目代码

题目

在数据结构中,哈希函数是用来将一个字符串(或任何其他类型)转化为小于哈希表大小且大于等于零的整数。一个好的哈希函数可以尽可能少地产生冲突。一种广泛使用的哈希函数算法是使用数值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和一个哈希表的大小,返回这个字符串的哈希值。

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

代码

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) {
        // write your code here
         int len = key.length;
        long hashcode = 0;
        long base = 1;
        for(int i=len-1;i>=0;i--){
            hashcode = hashcode  + Integer.valueOf(key[i])*base % HASH_SIZE;
            base = base *33% HASH_SIZE;
        }
        return (int)hashcode%HASH_SIZE;
    }
};
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) {
        // write your code here
        long ans = 0;
        for(int i = 0; i < key.length;i++) {
            ans = (ans * 33 + (int)(key[i])) % HASH_SIZE; 
        }
    return (int)ans;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏张泽旭的专栏

java计算奇数阶魔方阵

所谓“奇数阶魔方阵”是指n为不小于3的奇数的魔方阵。这类魔方阵的形式多样,这里我们仅讨论其中的一种形式的正规魔方阵。例如:3阶、5阶和7阶的魔方阵如图3 – 4...

12820
来自专栏程序生活

Python json 模块dumps、dump、loads、load的使用

本文主要讲下json.dumps和json.dump、json.loads和json.load的区别,因为经常需要加载json文件,读取数据,傻傻分不清...

9310
来自专栏PingCAP的专栏

TiDB 源码阅读系列文章(十三)索引范围计算简介

在数据库中处理查询请求时,如果可以尽早的将无关数据过滤掉,那么后续的算子就可以少做无用功,提升整个 SQL 的执行效率。过滤数据最常用的手段是使用索引,TiDB...

21040
来自专栏数据结构与算法

2806 红与黑 个人博客:doubleq.win

个人博客:doubleq.win 2806 红与黑  时间限制: 1 s  空间限制: 64000 KB  题目等级 : 白银 Silver 题解  查看运行结...

29940
来自专栏Golang语言社区

算法基础:最大递减数问题(Golang实现)

给出一个非负整数,找到这个非负整数中包括的最大递减数。一个数字的递减数是指相邻的数位从大到小排列的数字。 如: 95345323,递减数有:953,95,53,...

35050
来自专栏mathor

奇数魔方阵(奇数幻方)

16030
来自专栏desperate633

LeetCode 54. Spiral Matrixsolution

新建一个direction类,用它来控制坐标的移动,有两个函数,一个move,一个是turn。

8410
来自专栏null的专栏

挑战数据结构和算法——栈的push、pop序列

题目来源“数据结构与算法面试题80道”。在此给出我的解法,如你有更好的解法,欢迎留言。 ? 问题分析:本题考查栈的基本操作,栈是一种“先进后出”的数据结构。判...

34360
来自专栏机器学习入门

POJ 刷题系列:2965. The Pilots Brothers' refrigerator

POJ 刷题系列:2965. The Pilots Brothers’ refrigerator 传送门:POJ 2965. The Pilots Brothe...

20960
来自专栏GIS讲堂

Geohash之范围搜索

很多时候,我们都会遇到这样的需求:查找某个点周边多少距离的点。从本质来说,是一个缓冲区分析+空间查找,本文结合Geohash来实现类似的功能。

27340

扫码关注云+社区

领取腾讯云代金券