`
lobin
  • 浏览: 427252 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

一些有关哈希函数的随记

 
阅读更多

哈希函数

哈希函数

 

一个最简单最常见的哈希函数

 

 

int hash(int n, int m) {

    return n % m; // n & (m-1);

}

 

 

一个复杂的哈希函数

 

uint32_t hashint( uint32_t a)

{

a += ~(a<<15);

a ^=  (a>>10);

a +=  (a<<3);

a ^=  (a>>6);

a += ~(a<<11);

a ^=  (a>>16);

}

 

 

 

Java中用到的几个hash函数

 

 

 

static int hash(int h) {

// This function ensures that hashCodes that differ only by

// constant multiples at each bit position have a bounded

// number of collisions (approximately 8 at default load factor).

h ^= (h >>> 20) ^ (h >>> 12);

return h ^ (h >>> 7) ^ (h >>> 4);

}

 

 

 

 

 

 

 

private static int hash(int h) {

// Spread bits to regularize both segment and index locations,

// using variant of single-word Wang/Jenkins hash.

h += (h <<  15) ^ 0xffffcd7d;

h ^= (h >>> 10);

h += (h <<   3);

h ^= (h >>>  6);

h += (h <<   2) + (h << 14);

return h ^ (h >>> 16);

}

 

Java hash code默认实现

在Java中,Object是所有java类的基类,其中定义了一个hashCode方法,在子类中如果没有重写hashCode方法,都通过Object的hashCode方法计算hashCode:

 

 

public native int hashCode();
 它是一个native方法,由jvm实现。具体实现在Object.c,在jdk\src\share\native\java\lang目录下。

 

 

 

static JNINativeMethod methods[] = {
    {"hashCode",    "()I",                    (void *)&JVM_IHashCode},
    {"wait",        "(J)V",                   (void *)&JVM_MonitorWait},
    {"notify",      "()V",                    (void *)&JVM_MonitorNotify},
    {"notifyAll",   "()V",                    (void *)&JVM_MonitorNotifyAll},
    {"clone",       "()Ljava/lang/Object;",   (void *)&JVM_Clone},
};
 从上面看hashCode方法具体由JVM_IHashCode实现。

 

 

JVM_IHashCode方法:

 

JVM_ENTRY(jint, JVM_IHashCode(JNIEnv* env, jobject handle))
  JVMWrapper("JVM_IHashCode");
  // as implemented in the classic virtual machine; return 0 if object is NULL
  return handle == NULL ? 0 : ObjectSynchronizer::FastHashCode (THREAD, JNIHandles::resolve_non_null(handle)) ;
JVM_END
 需要展开来看。展开后主要代码在:
return handle == NULL ? 0 : ObjectSynchronizer::FastHashCode (THREAD, JNIHandles::resolve_non_null(handle)) ;
 

 

FastHashCode方法:

 

intptr_t ObjectSynchronizer::FastHashCode (Thread * Self, oop obj) {
  if (UseBiasedLocking) {
    // NOTE: many places throughout the JVM do not expect a safepoint
    // to be taken here, in particular most operations on perm gen
    // objects. However, we only ever bias Java instances and all of
    // the call sites of identity_hash that might revoke biases have
    // been checked to make sure they can handle a safepoint. The
    // added check of the bias pattern is to avoid useless calls to
    // thread-local storage.
    if (obj->mark()->has_bias_pattern()) {
      // Box and unbox the raw reference just in case we cause a STW safepoint.
      Handle hobj (Self, obj) ;
      // Relaxing assertion for bug 6320749.
      assert (Universe::verify_in_progress() ||
              !SafepointSynchronize::is_at_safepoint(),
             "biases should not be seen by VM thread here");
      BiasedLocking::revoke_and_rebias(hobj, false, JavaThread::current());
      obj = hobj() ;
      assert(!obj->mark()->has_bias_pattern(), "biases should be revoked by now");
    }
  }

  // hashCode() is a heap mutator ...
  // Relaxing assertion for bug 6320749.
  assert (Universe::verify_in_progress() ||
          !SafepointSynchronize::is_at_safepoint(), "invariant") ;
  assert (Universe::verify_in_progress() ||
          Self->is_Java_thread() , "invariant") ;
  assert (Universe::verify_in_progress() ||
         ((JavaThread *)Self)->thread_state() != _thread_blocked, "invariant") ;

  ObjectMonitor* monitor = NULL;
  markOop temp, test;
  intptr_t hash;
  markOop mark = ReadStableMark (obj);

  // object should remain ineligible for biased locking
  assert (!mark->has_bias_pattern(), "invariant") ;

  if (mark->is_neutral()) {
    hash = mark->hash();              // this is a normal header
    if (hash) {                       // if it has hash, just return it
      return hash;
    }
    hash = get_next_hash(Self, obj);  // allocate a new hash code
    temp = mark->copy_set_hash(hash); // merge the hash code into header
    // use (machine word version) atomic operation to install the hash
    test = (markOop) Atomic::cmpxchg_ptr(temp, obj->mark_addr(), mark);
    if (test == mark) {
      return hash;
    }
    // If atomic operation failed, we must inflate the header
    // into heavy weight monitor. We could add more code here
    // for fast path, but it does not worth the complexity.
  } else if (mark->has_monitor()) {
    monitor = mark->monitor();
    temp = monitor->header();
    assert (temp->is_neutral(), "invariant") ;
    hash = temp->hash();
    if (hash) {
      return hash;
    }
    // Skip to the following code to reduce code size
  } else if (Self->is_lock_owned((address)mark->locker())) {
    temp = mark->displaced_mark_helper(); // this is a lightweight monitor owned
    assert (temp->is_neutral(), "invariant") ;
    hash = temp->hash();              // by current thread, check if the displaced
    if (hash) {                       // header contains hash code
      return hash;
    }
    // WARNING:
    //   The displaced header is strictly immutable.
    // It can NOT be changed in ANY cases. So we have
    // to inflate the header into heavyweight monitor
    // even the current thread owns the lock. The reason
    // is the BasicLock (stack slot) will be asynchronously
    // read by other threads during the inflate() function.
    // Any change to stack may not propagate to other threads
    // correctly.
  }

  // Inflate the monitor to set hash code
  monitor = ObjectSynchronizer::inflate(Self, obj);
  // Load displaced header and check it has hash code
  mark = monitor->header();
  assert (mark->is_neutral(), "invariant") ;
  hash = mark->hash();
  if (hash == 0) {
    hash = get_next_hash(Self, obj);
    temp = mark->copy_set_hash(hash); // merge hash code into header
    assert (temp->is_neutral(), "invariant") ;
    test = (markOop) Atomic::cmpxchg_ptr(temp, monitor, mark);
    if (test != mark) {
      // The only update to the header in the monitor (outside GC)
      // is install the hash code. If someone add new usage of
      // displaced header, please update this code
      hash = test->hash();
      assert (test->is_neutral(), "invariant") ;
      assert (hash != 0, "Trivial unexpected object/monitor header usage.");
    }
  }
  // We finally get the hash
  return hash;
}

 

Park–Miller random number generator

 

The Lehmer random number generator[1] (named after D. H. Lehmer), sometimes also referred to as the Park–Miller random number generator(after Stephen K. Park and Keith W. Miller), is a type of linear congruential generator (LCG) that operates in multiplicative group of integers modulo n. The general formula is:

 

X(k+1) = g.X(k) mod n

 

where the modulus n is a prime number or a power of a prime number, the multiplier g is an element of high multiplicative order modulo n (e.g., a primitive root modulo n), and the seed X0 is coprime to n.

 

 

 

 

 

 

 

加密hash函数和非加密hash函数(cryptographic hash function &non-cryptographic hash function)

 

 

哈希函数设计的目的以及可能的问题

 

碰撞

 

冲突(Collision也就是产生碰撞

 

 

碰撞是怎么回事,是怎么产生的?

 

 

int hash(int n, int m) {

    return n % m; // n & (m-1);

}

假设m4,输入n0123计算出来的哈希值(0123)能散列到不同的bucket中,但输入n4567计算出来的哈希值(0123)又散列到这些bucket,规律是输入的nn + 4 x ii0…k)的这些输入计算出来的哈希值都相同,这就是所说的冲突(Collision或碰撞

 

 

冲突(Collision有什么问题

 

 

 

 

成功构造出大量使hash表发生碰撞的元素,导致系统被DoS

 

 

 

 

 

历史上就出现过利用Linux内核hash函数的漏洞,成功构造出大量使hash表发生碰撞的元素,导致系统被DoS,所以目前内核的大部分hash函数都有一个随机数作为参数进行掺杂,以使其最后的值不能或者是不易被预测。

 

 

 

 

这个问题放在现在是很难碰到了,基本上不可能Dos到系统被攻击的程度。

 

冲突(Collision解决办法

 

 

雪崩效应

 

什么是雪崩效应

 

Full avalanche says that differences in any input bit can cause differences in any output bit.

 

 

 

 

哈希函数设计的考虑

 

 

性能

哈希函数需要设计得更好的性能, 效率高

 

单向

 

用随机数进行掺杂

 

 

目前Linux内核的大部分hash函数都有一个随机数作为参数进行掺杂,以使其最后的值不能或者是不易被预测。

 

 

 

安全性

 

 

 

 

 

加密hash函数

 

 

非加密hash函数

 

 

 

单向hash函数

 

有真正意义上的单向hash函数吗?

Leslie Lamport在Constructing Digital Signatures from a One Way Function中 写道
A one way function is a function that is easy to compute, but whose
inverse is difficult to compute [1]. More precisely a one way function f is
a function from a set of data objects to a set of values having the following

two properties:

1. Given any value v , it is computationally infeasible to find a
data object d such that f(d) = v .
2. Given any data object d , it is computationally infeasible to find
a different data object d' such that f(d') = f(d) .

If the set of data objects is larger than the set of values, then such a
function is sometimes called a one way hashing function.

 

 

 哈希签名:哈希函数(hash)在数字签名中的实现思路

 

参考文章:https://lobin.iteye.com/blog/2436715

 

CRC

https://www.kernel.org/doc/Documentation/crc32.txt

 

参考资料

<!--[if !supportLists]-->1、  <!--[endif]-->http://burtleburtle.net/bob/hash/integer.html

<!--[if !supportLists]-->2、  <!--[endif]-->https://naml.us/tags/thomas-wang/

<!--[if !supportLists]-->3、  <!--[endif]-->http://blog.reverberate.org/2012/01/state-of-hash-functions-2012.html

<!--[if !supportLists]-->4、  <!--[endif]-->https://opensource.googleblog.com/2011/04/introducing-cityhash.html

<!--[if !supportLists]-->5、  <!--[endif]-->https://en.wikipedia.org/wiki/Jenkins_hash_function

<!--[if !supportLists]-->6、  <!--[endif]-->https://en.wikipedia.org/wiki/CityHash

 

<!--[if !supportLists]-->7、  <!--[endif]-->https://en.wikipedia.org/wiki/One-way_function

8、Constructing Digital Signatures from a One Way Function, http://lamport.azurewebsites.net/pubs/pubs.html#dig-sig

9、Constructing Digital Signatures from a One Way Function, http://lamport.azurewebsites.net/pubs/dig-sig.pdf

0
0
分享到:
评论

相关推荐

    哈希函数的应用(数据结构课程设计)

    在本文中,我们将探讨哈希函数的应用的一些方面,并设计一个基于哈希函数的查找系统。 哈希函数的定义 哈希函数是一种将输入值(通常是字符串或数字)映射到固定长度的输出值的函数。哈希函数的输出值称为哈希值或...

    一些经典简单的哈希函数

    哈希函数简介 哈希函数是计算机科学中的一种常用技术,用于将输入数据转换为固定长度的输出,即哈希值。哈希函数的主要应用场景包括哈希表、数据压缩、数字签名、身份验证等。 在给定的文件中,我们可以看到多种...

    常用哈希函数结构 数据结构

    在IT领域,特别是数据结构与算法中,哈希函数扮演着至关重要的角色。它们被广泛应用于各种场景,如数据库索引、密码存储、缓存管理等,以提高数据检索的速度和效率。本文将深入探讨几种常用的哈希函数,包括SDBMHash...

    哈希函数与数据完整性

    ### 哈希函数与数据完整性 #### 一、哈希函数的概念 ##### 1.1 基本思想 哈希函数的核心思想是通过一个特定的算法将任意长度的数据映射为固定长度的输出(通常称为哈希值或者摘要)。这种映射具有一个重要的特性...

    字符串哈希函数设计

    字符串哈希函数是一种在计算机科学中用于快速查找和比较字符串的有效方法。它的核心思想是将一个字符串转换为一个整数值,这个数值可以作为字符串的一种紧凑表示,便于存储、比较和查找。在本实验中,我们将关注如何...

    散列表(哈希函数)电话簿通讯录

    哈希函数设计的目标是确保不同的输入会产生不同的哈希值,尽管在实际应用中可能会出现哈希冲突,即不同的输入产生了相同的哈希值。当冲突发生时,有多种解决策略,如开放寻址法、链地址法或再哈希法。 在这个电话簿...

    从标准假设中保留属性的哈希函数_Property-Preserving Hash Functions from Standard

    《从标准假设中保留属性的哈希函数》这篇论文探讨了一种特殊类型的哈希函数——属性保留哈希函数(Property-Preserving Hash Functions),这种函数能够在压缩输入数据的同时,保持某些特定属性,允许在仅知道哈希值...

    哈希函数和时序关联规则

    ### 哈希函数与时序关联规则 #### 引言 随着信息技术的快速发展和数据库技术的广泛应用,数据挖掘作为一种从海量数据中提取有价值信息的技术,已成为研究热点。特别是关联规则挖掘,它能够揭示出数据之间的有趣关系...

    哈希函数&MD5.doc

    ### 哈希函数及其应用 #### 一、哈希函数概述 哈希函数作为一种重要的密码...然而,随着技术的发展,一些哈希函数(如MD5)的安全性受到了挑战,因此在实际应用中选择更加安全的哈希算法(如SHA系列)是非常必要的。

    用C语言实现常用的字符串哈希函数

    用C语言实现常用的字符串哈希函数,比如RSHash、JSHash、PJWHash、FNVHash等

    易语言PHP哈希函数

    2. 数据预处理:在计算哈希值之前,可能需要对输入数据进行一些预处理,如添加填充符、转换为二进制等。 3. 位运算:HashPJW算法会用到位移、位与、位或等操作,这些都是易语言中的基本操作符。 4. 循环计算:哈希...

    完美哈希函数的实现

    用C++实现的完美哈希函数,打印C语言的32个关键字的哈希值,并且判断所输入的字符串是否为关键字

    用C语言实现MD5哈希函数

    用C语言实现MD5哈希函数,它是将文件的每一行进行MD5加密,输出一个128位的哈希值。

    数据结构课程设计-哈希函数的应用

    数据结构课程设计-哈希函数的应用 本资源摘要信息是关于数据结构课程设计中哈希函数的应用的知识点总结。哈希函数是将关键字映射到哈希表中的一个函数,它的应用在数据结构中非常重要。本文将从哈希函数的定义、...

    易语言源码PHP哈希函数易语言源码.rar

    哈希函数,也称为散列函数,是一种将任意长度的输入(也叫做预映射)通过算法变换成固定长度输出的函数。在PHP中,哈希函数广泛用于数据验证、存储和加密。例如,密码通常会通过哈希函数进行处理,以保护用户信息的...

    哈希函数和数字签名概述.pdf

    "哈希函数和数字签名概述" 哈希函数和数字签名是信息安全中两个重要的概念。哈希函数是一种将任意长度的消息映射成一个较短的定长输出报文的函数,而数字签名则是一种使用私钥对消息进行 签名的方式,以证明消息的...

Global site tag (gtag.js) - Google Analytics