100 milyon dize 100 bin int nasıl eşlenir?

Question

Yaklaşık 100 milyon basit anahtar/değer çiftine sahibim (eski veriler, hiçbir zaman güncellenmesi gerekmez ve anahtarlar rastgele bir dizedir) ve bunları sorgu için redis'te saklamak istiyorum.

İlk dört karakteri bir hash anahtarı olarak kullanıyorum ve bunları bir karma türünde saklıyorum, bu yüzden her bir karma anahtarın yaklaşık 1000 alt anahtarıyla birlikte, yaklaşık bir milyon karma anahtarın var.

Ancak işler sadece planlı olarak gitmez. Bazı nedenlerden dolayı, bazı karma anahtarların yalnızca bir alt anahtarının olduğunu buldum, ancak bazılarında bellekte kodlanamayan 500.000'den fazla alt anahtar var.

Bu yüzden 100 milyon dizimi ortalama 100 bin kanala (int) ayırabilen bazı basit anlaşılır algoritmalar olduğunu bilmek isterim. Bir ipi aldığımda, aynı algoritmayı kullanarak nereye gittiğini bilebilirim.

Teşekkürler!

Answer 1

Karma dizesini hesaplamak için dizenin yalnızca küçük bir bölümünü kullanmak sorun olabilir, çünkü dizeleriniz aynı önekleri paylaşabilir.

Tüm dizeyi http://www.javamex.com/tutorials/collections/hash_function_technical_2.shtml ve Good Hash Function for Strings (aslında aynı işlevden iki farklı açıklama vererek) içeren bir dizi sağlama işlevleri açıklanmaktadır.

Buna bakmanın bir yolu, bir dizenin karakterlerini A + Bx + Cx^2 + Dx^3 ... biçimindeki bir polinom A, B, C katsayıları olarak kabul eder. x durumu 31 ve aritmetik modulo 2^32'dir. Eğer x iyi seçilmişse, bu bir çok deneyimin olduğu ve bazı matematiklerin geçerli olabileceği ve iyi özelliklere sahip olduğu bir şemadır. Daha da iyisi, aritmetik moduloyu hash tablosunun büyüklüğünü yapmak ve bir asal olmak için hash tablosunun boyutunu seçmektir. Verileriniz statikse, tercih ettiğiniz tablo boyutu ve birkaç farklı x değerine göre birkaç farklı prim denemeye değer olabilir ve size en eşit şekilde doldurulmuş tabloyu veren kombinasyonu seçin.