Knut's Multiplicative Method

Giriş
Bu yöntem aynı zamanda Fibonacci Hashing olarak ta bilinir. Sabitin nereden geldiğinin açıklaması şöyle.

0x9e3779b9 is the integral part of the Golden Ratio's fractional part 0.61803398875… (sqrt(5)-1)/2, multiplied by 2^32.
...
This method is often referred to as "Golden Ratio Hashing", or "Fibonacci Hashing" and was popularised by Donald Knuth (The Art of Computer Programming: Volume 3: Sorting and Searching).

Bu denklemde kullanılan 0x9E3779B1 sabiti, boost içinde kullanılan 0x9E3779B9 değerine çok yakın. Açıklaması şöyle.

Occasionally, you may also see 0x9e3779b1, which is the prime closest to 0x9e3779b9 (and appears to be a bit of "cargo cult" as this is not a modular hash). Similarly, 0x9e3779b97f4a7c15 and 0x9e3779b97f4a7c55 are the 64 bit equivalents of these numbers.

Örnek - Asal Sayı
Şöyle yaparız

hash(i)=i*0x9e3779b1 mod 2^32 

Örnek - Asal Sayı
Şöyle yaparız.

hash = n * 0x9e3779b1 >>> 24

Örnek - Asal Sayı
C ile Şöyle yaparız. Burada % N işlemi ile bir bucket'a dönüştürme yok

uint32_t hash(uint32_t v)
{
    return v * UINT32_C(2654435761);
    // do not comment about the lack of right shift. I'm not ignoring it. read on.
}

Örnek - Asal Sayı
Java ile şöyle yaparız.

public long hash(int key) {
    long l = 2654435769L;
    return (key * l >> 32) % N ;
}

Kripto

Giriş
Hash, CRC ve Kripto ile ilgili aldığım notlar aşağıda.

Hash'lenen Değerin Bit Uzunluğu/Hash Bit Uzunluğu
Basit bir kural şu. Eğer hash'lenen değerin bit uzunluğu hash'in bit uzunluğundan büyük ise mutlaka çarpışma (collision) olacaktır. Zaten hiç bir hash mükemmel olmadığı çarpışma olması kaçınılmazdır.

Tek Yönlü Hash
Hash'ler tek yönlüdür ve güvenlik için 70'lerden beri kullanılırlar. 90'larda salt + hash şeklinde kullanımı başlamıştır. Iterative hash'ler ise 2010'lardan itibaren kullanılıyorlar.

Standart Hash Fonksiyonları
Gömülü Proje - Hash yazısına taşıdım.

Basit Hash Fonksiyonları
Additive Hash
Çok basit olduğu ve iyi bir dağılım sağlamadığı söyleniyor. İyi bir dağılım sağlamamasının sebebi "abc" ve "cba" ve "cab" için aynı değeri dönmesi. Yani "commutative operation", türkçesi "değişme özelliği" 'ni dikkate almaması.

Örnek: ub4 unsigned integer olarak düşünülebilir.

Sum of Squares
Bu hash yöntemi pek yaygın değil ancak kullanıldığını gördüğüm için not etmek istedim. 
Multiplicative hash is sum of the squares of all bytes. Örnek:
unsigned  hash_func (char* string, unsigned len) {
  unsigned sum = 0;
  unsigned value = 0;
  for (; len > 0; len --) {
    value = (unsigned) (*string++ & 0xFF)
    sum += value * value;
  }
  return sum;
}


Rotating Hash
XOR hash'e göre biraz daha iyi. Örnek:

Knut's Multiplicative Method
Knut's Multiplicative Method yazısına taşıdım.


Programlama Dillerinde Bulunan Hash Gerçekleştirimleri
Java
Javadaki basit bir hash fonksiyonu için buraya bakabilirsiniz. Fonksiyonun yaptığı şey verilen değerin belli alanlarından bitleri almak ve bunları XOR'lamak .

Buradaki soruda XOR ile bitlerin daha iyi dağılım gösterdiği yazılı.XOR'lamanın tek problem XOR'un simetrik olması. Yani a.hashCode() ^ b.hashCode() ve b.hashCode() ^ a.hashCode() aynı değeri verir.
Ama bence bu büyük bir problem değil.

C++
STL ile std::hash<T> metodu geliyor.Bu metodun generic çalışmasına dikkat çekilmiş.
Örnek:

std::hash<std::string> str_hash;
std::string str1 = "Test";
size_t hash = str_hash (str1);

std::hash() farklı arka arkaya çağırılarak bir seed değerine combine işlemini gerçekleştiremiyor. boost kütüphanesi ile gelen hash_combine() metodu ile bu iş çok kolay. Eğer boost kullanmak istemiyorsak aşağıdaki generic kod kullanarak yapılabilir.

template <class T>
inline void hash_combine(std::size_t & seed, const T & v)
{
  std::hash<T> hasher;
  seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

namespace std
{
  template<typename S, typename T> struct hash<pair<S, T>>
  {
    inline size_t operator()(const pair<S, T> & v) const
    {
      size_t seed = 0;
      ::hash_combine(seed, v.first);
      ::hash_combine(seed, v.second);
      return seed;
    }
  };
}

Boost
hash_combine ile mevcut değer bir başka değer ile birleştiriliyor. Kullanılan formüldeki sabit burada açıklanıyor.

hash_combine metodunu kullanmak için hash.hpp dosyasını dahil etmek gerekir.

#include <unordered_map>
#include <boost/functional/hash.hpp>

using namespace std;
using namespace boost;

unordered_map<pair<int, int>, int, hash<pair<int, int>>> table;

Bir başka örnek:

#include <boost/functional/hash.hpp>
size_t  seed = 0;
int val = //...
boost::hash_combine (seed,val);

Kriptografik Hash Fonksiyonları



MD5 - Kullanmayın
MD5 yazısına taşıdım

SHA-0
SHA-0 yazısına taşıdım.

SHA-1 - Kullanmayın
SHA-1 yazına taşıdım.

SHA-2
SHA-2 yazısına taşıdım.

CRC Fonksiyonları
Checksum başlıklı yazıya taşıdım.

Pairing Fonksiyonları
Pairin Fonksiyonları Hash ve CRC gibi verilen veriden başka bir sayı üretir. Ancak diğerlerinden farklı olarak üretilen sayıdan daha sonra geriye dönerek veriyi elde etmek mümkün.

Belli Aralıktaki İki Sayıyı Birleştirmek
Aşağıda 0 - 100,000 arasındaki sayıları birleştiren ve tekrar ayıran bir örnek var.

Define f(n,m)=n+1000000m. Then n=f(n,m)mod1000000, and m=f(n,m)−n1000000.

Bu örneği genel bir formül haline getirmek istersek:

Bit Kaydırma Yöntemi
İki byte olduğunu bildiğimiz iki sayıyı dört byte'a sığdırmak mümkün. Örnek:

KRİPTOLAR
Her kriptoda confidentiality (mesajın istenmeyen birisi tarafından okunamamasını ağlamak) ve authenticity (belirtilen kişiden geldiğini doğrulamak) önem taşır.

Confidentiality için gönderen alıcının public anahtarını kullanarak mesajı şifreler.

Authentication için mesajın imzalanması (signing) gerekir. İmza için mesajı gönderen kendi private anahtarını kullanır. Alıcı tarafa gönderenin public anahtarı ile mesajı doğrular.

Diffie-Hellman
Diffie-Hellman yazısına taşıdımö

DES
DES yazısına taşıdım.

AES
AES yazısına taşıdım.

RSA
RSA yazısına taşıdım.

Gömülü Proje - Hash

Giriş
Bu hash fonksiyonları kriptografik değildir! Dolasıyıla avalance effect göstermelerini beklememek gerekir.

DJB2, DJB2a, FNV-1,FNV-1a, Murmur2, MurmurHash3 gibi bir çok popüler hash fonksiyonu mevcut.

FNV1

FNV1 ve FNV1-a kodlaması çok basit hash metodları. 

FNV1-a aşağıdaki gibi. FNV1 ile tek farkı xor işleminin prime ile çarpılmasından önce yapılması.

hash = FNV_offset_basis
for each octetOfData to be hashed
    hash = hash xor octetOfData
    hash = hash * FNV_prime
return hash

FNV1 ve FNV1-a için sabitler aşağıda.

Hash Size    Prime                       Offset
===========  =========================== =================================
32-bit       16777619                    2166136261
64-bit       1099511628211               14695981039346656037

Murmur3
Şöyle yaparız.

uint64_t MurmurHash3Mixer( uint64_t key ) { 
  key ^= (key >> 33);
  key *= 0xff51afd7ed558ccd;
  key ^= (key >> 33);
  key *= 0xc4ceb9fe1a85ec53;
  key ^= (key >> 33);

  return key;
}