一些有关哈希函数的随记

哈希函数

哈希函数

 

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

 

 

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);

}

假设m＝4，输入n＝0，1，2，3计算出来的哈希值（0，1，2，3）能散列到不同的bucket中，但输入n＝4，5，6，7计算出来的哈希值（0，1，2，3）又散列到这些bucket，规律是输入的n＝n + 4 x i（i＝0…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