Fungsi Hash Bagus untuk String

Saya mencoba memikirkan fungsi hash yang baik untuk string. Dan saya berpikir mungkin ide yang baik untuk merangkum nilai unicode untuk lima karakter pertama dalam string (dengan asumsi itu memiliki lima, jika tidak hentikan di mana itu berakhir). Apakah itu ide yang bagus, atau itu ide yang buruk?

Saya melakukan ini di Jawa, tetapi saya tidak akan membayangkan itu akan membuat banyak perbedaan.

Biasanya hash tidak akan melakukan penjumlahan, sebaliknya stopdan potsakan memiliki hash yang sama.

dan Anda tidak akan membatasi ke karakter n pertama karena jika tidak rumah dan rumah akan memiliki hash yang sama.

Umumnya hash mengambil nilai dan mengalikannya dengan bilangan prima (membuatnya lebih mungkin untuk menghasilkan hash unik) Jadi Anda bisa melakukan sesuatu seperti:

int hash = 7;
for (int i = 0; i < strlen; i++) {
    hash = hash*31 + charAt(i);
}

Jika ini masalah keamanan, Anda bisa menggunakan Java crypto:

import java.security.MessageDigest;

MessageDigest messageDigest = MessageDigest.getInstance("SHA-256");
messageDigest.update(stringToEncrypt.getBytes());
String encryptedString = new String(messageDigest.digest());

Anda mungkin harus menggunakan String.hashCode () .

Jika Anda benar-benar ingin menerapkan kode hash:

Jangan tergoda untuk mengecualikan bagian penting dari objek dari perhitungan kode hash untuk meningkatkan kinerja - Joshua Bloch, Java Efektif

Menggunakan hanya lima karakter pertama adalah ide yang buruk . Pikirkan tentang nama hierarkis, seperti URL: mereka semua akan memiliki kode hash yang sama (karena semuanya dimulai dengan "http: //", yang berarti mereka disimpan di bawah ember yang sama di peta hash, menunjukkan kinerja yang buruk.

Berikut adalah kisah perang yang diparafrasekan pada Kode hash dari " Java Efektif ":

Fungsi hash String diimplementasikan dalam semua rilis sebelum 1.2 memeriksa paling banyak enam belas karakter, spasi secara merata di seluruh string, dimulai dengan karakter pertama. Untuk koleksi besar nama hierarkis, seperti URL, fungsi hash ini menampilkan perilaku buruk.

Jika Anda melakukan ini di Jawa maka mengapa Anda melakukannya? Panggil saja .hashCode()string

HashFunction( Javadoc ) jambu biji menyediakan hashing non-crypto-kuat yang layak.

Fungsi yang disediakan oleh Nick ini bagus tetapi jika Anda menggunakan String baru (byte [] byte) untuk melakukan transformasi ke String, gagal. Anda dapat menggunakan fungsi ini untuk melakukan itu.

private static final char[] hex = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };

public static String byteArray2Hex(byte[] bytes) {
    StringBuffer sb = new StringBuffer(bytes.length * 2);
    for(final byte b : bytes) {
        sb.append(hex[(b & 0xF0) >> 4]);
        sb.append(hex[b & 0x0F]);
    }
    return sb.toString();
}

public static String getStringFromSHA256(String stringToEncrypt) throws NoSuchAlgorithmException {
    MessageDigest messageDigest = MessageDigest.getInstance("SHA-256");
    messageDigest.update(stringToEncrypt.getBytes());
    return byteArray2Hex(messageDigest.digest());
}

Mungkin ini bisa membantu seseorang

// djb2 hash function
unsigned long hash(unsigned char *str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}

sumber Logika di balik fungsi hash djb2 - SO

FNV-1 dikabarkan sebagai fungsi hash yang bagus untuk string.

Untuk string panjang (lebih lama dari, katakanlah, sekitar 200 karakter), Anda bisa mendapatkan kinerja yang baik dari fungsi hash MD4 . Sebagai fungsi kriptografi, itu rusak sekitar 15 tahun yang lalu, tetapi untuk tujuan non kriptografi, masih sangat baik, dan sangat cepat. Dalam konteks Java, Anda harus mengubah nilai 16-bit charmenjadi kata-kata 32-bit, misalnya dengan mengelompokkan nilai-nilai tersebut menjadi pasangan. Implementasi MD4 yang cepat di Java dapat ditemukan di sphlib . Mungkin berlebihan dalam konteks tugas kelas, tetapi patut dicoba.

Jika Anda ingin melihat implementasi standar industri, saya akan melihat java.security.MessageDigest .

"Intisari pesan adalah fungsi hash satu arah yang aman yang mengambil data berukuran sewenang-wenang dan menghasilkan nilai hash panjang tetap."

inilah tautan yang menjelaskan banyak fungsi hash yang berbeda, untuk saat ini saya lebih suka fungsi hash ELF untuk masalah khusus Anda. Dibutuhkan sebagai input string yang panjang sewenang-wenang.

sdbm: algoritma ini dibuat untuk pustaka basis data sdbm (implementasi domain publik dari ndbm)

static unsigned long sdbm(unsigned char *str)
{   
    unsigned long hash = 0;
    int c;
    while (c = *str++)
            hash = c + (hash << 6) + (hash << 16) - hash;

    return hash;
}

         public String hashString(String s) throws NoSuchAlgorithmException {
    byte[] hash = null;
    try {
        MessageDigest md = MessageDigest.getInstance("SHA-256");
        hash = md.digest(s.getBytes());

    } catch (NoSuchAlgorithmException e) { e.printStackTrace(); }
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < hash.length; ++i) {
        String hex = Integer.toHexString(hash[i]);
        if (hex.length() == 1) {
            sb.append(0);
            sb.append(hex.charAt(hex.length() - 1));
        } else {
            sb.append(hex.substring(hex.length() - 2));
        }
    }
    return sb.toString();
}

Merupakan ide bagus untuk bekerja dengan angka ganjil ketika mencoba mengembangkan fungsi string yang baik. fungsi ini mengambil string dan mengembalikan nilai indeks, sejauh ini kerjanya cukup baik. dan memiliki sedikit tabrakan. indeks berkisar dari 0 - 300 mungkin bahkan lebih dari itu, tetapi saya belum mendapatkan yang lebih tinggi sejauh ini bahkan dengan kata-kata panjang seperti "teknik elektromekanis"

int keyHash(string key)
{
    unsigned int k = (int)key.length();
    unsigned int u = 0,n = 0;

    for (Uint i=0; i<k; i++)
    {
        n = (int)key[i];
        u += 7*n%31;
    }
    return u%139;
}

Hal lain yang dapat Anda lakukan adalah mengalikan setiap karakter int parse dengan indeks karena bertambah seperti kata "beruang" (0 * b) + (1 * e) + (2 * a) + (3 * r) yang akan memberi Anda nilai int untuk bermain. fungsi hash pertama di atas bertabrakan pada "di sini" dan "mendengar" tetapi masih hebat dalam memberikan beberapa nilai unik yang baik. yang di bawah ini tidak bertabrakan dengan "di sini" dan "dengar" karena saya melipatgandakan setiap karakter dengan indeks saat itu meningkat.

int keyHash(string key)
{
    unsigned int k = (int)key.length();
    unsigned int u = 0,n = 0;

    for (Uint i=0; i<k; i++)
    {
        n = (int)key[i];
        u += i*n%31;
    }
    return u%139;
}

Berikut adalah fungsi hash sederhana yang saya gunakan untuk tabel hash yang saya buat. Pada dasarnya untuk mengambil file teks dan menyimpan setiap kata dalam indeks yang mewakili urutan abjad.

int generatehashkey(const char *name)
{
        int x = tolower(name[0])- 97;
        if (x < 0 || x > 25)
           x = 26;
        return x;
}

Apa yang pada dasarnya dilakukan adalah kata-kata dipotong menurut huruf pertama mereka. Jadi, kata yang dimulai dengan 'a' akan mendapatkan kunci hash 0, 'b' akan mendapatkan 1 dan seterusnya dan 'z' akan menjadi 25. Angka dan simbol akan memiliki kunci hash 26. Ada keuntungan yang disediakan oleh ini ; Anda dapat menghitung dengan mudah dan cepat di mana kata yang diberikan akan diindeks dalam tabel hash karena semuanya dalam urutan abjad, seperti ini: Kode dapat ditemukan di sini: https://github.com/abhijitcpatil/general

Memberikan teks berikut sebagai masukan: Suatu hari Atticus berkata kepada Jem, “Aku lebih suka kamu menembak kaleng di halaman belakang, tapi aku tahu kamu akan mengejar burung. Tembak semua blue jay yang Anda inginkan, jika Anda bisa mengenai mereka, tapi ingat itu dosa membunuh burung mockingbird. ” Itulah satu-satunya saat saya mendengar Atticus mengatakan itu dosa untuk melakukan sesuatu, dan saya bertanya kepada Miss Maudie tentang hal itu. "Ayahmu benar," katanya. “Mockingbird tidak melakukan satu hal selain membuat musik untuk kita nikmati. Mereka tidak memakan kebun orang, tidak bersarang di boks jagung, mereka tidak melakukan satu hal selain menyanyikan hati mereka untuk kita. Itu sebabnya membunuh burung mockingbird adalah dosa.

Ini akan menjadi output:

0 --> a a about asked and a Atticus a a all after at Atticus
1 --> but but blue birds. but backyard
2 --> cribs corn can cans
3 --> do don’t don’t don’t do don’t do day
4 --> eat enjoy. except ever
5 --> for for father’s
6 --> gardens go
7 --> hearts heard hit
8 --> it’s in it. I it I it’s if I in
9 --> jays Jem
10 --> kill kill know
11 --> 
12 --> mockingbird. music make Maudie Miss mockingbird.”
13 --> nest
14 --> out one one only one
15 --> people’s
16 --> 17 --> right remember rather
18 --> sin sing said. she something sin say sin Shoot shot said
19 --> to That’s their thing they They to thing to time the That to the the tin to
20 --> us. up us
21 --> 
22 --> why was was want
23 --> 
24 --> you you you’ll you
25 --> 
26 --> “Mockingbirds ” “Your ‘em “I’d

Ini akan menghindari tabrakan dan itu akan cepat sampai kita menggunakan pergeseran dalam perhitungan.

 int k = key.length();
    int sum = 0;
    for(int i = 0 ; i < k-1 ; i++){
        sum += key.charAt(i)<<(5*i);
    }