Dotaz: Java - jak vygenerovat hash určité délky

[tmr]

Dobrý den,

potřeboval bych v Javě napsat funkci, které budu předávat 2 parametry - string který se má hashovat a délku výsledného hashe (délka dejme tomu v desítkovém zápisu). Takže když zavolám get_hash("pokus", 4), tak dostanu třeba "2849". Jak to mám udělat?

Odpovědi

[moira]

K čemu to má být dobré?

[tmr]

Ne, že bych tuhle otázku nečekal To je na delší povídání, v podstatě jde o to že uživatel bude muset ten hash opsat z webu do mobilu, takže dlouhý hash nebude zrovna to pravé. Napadlo mě jedno řešení - vzít třeba jenom prvních x cifer z MD5 hashe, to by snad mělo stačit...

[Konqui]

A musí to být hash nebo stačí jen náhodné čísla/písmena o určité délce?

[tmr]

Hash

[moira]

Škoda, že když jsi tu otázku čekal, tak jsi rovnou nenapsal odpověď do dotazu :) Ptal jsem se proto, protože není hash jako hash a ne každý se hodí ke všemu. Problém podobných dotazů jako jsi položil je v tom, že dotazující si na řešení problému zvolí nějaké řešení (dost často naprosto nevhodné nebo zbytečně složité) a na to se rovnou zeptá. Bohužel místo toho, aby se zeptal na řešení původního problému. Pak přestože existuje spousta jiných a jednodušších cest, tak mu s pak už nikdo neporadí, protože netuší, co chtěl tazatel vlastně vyřešit. Jak vidíš, sám jsi nakonec přišel na mnohem jednodušší řešení, které ale mimochodem nepasuje na původní dotaz :)

[tmr]

Mě napadlo, že se na tohle někdo zeptá, až po odeslání dotazu Jinak souhlasím, že je lepší ptát se na původní problém, normálně bych to udělal, teď ale dělám na progamu pro jednu firmu a nemůžu mluvit o tom co přesně dělám.

[Konqui]

A o jak dlouhý text se zhruba bude jednat? Napadá mě jedině napsat si vlastní hashovací funkci (pokud to má být rozumně krátké)

[kulik]

Vezmi hodnotu hashcode() toho stringu a uprav si ji dle chuti, napriklad pro tento konkretni pripad modulo 10000.

[retroslava]

A není škoda z delšího hashe ztratit jeho část ? Nebylo by lepší (ale jistě pomalejší) hash rozdělit na dvě půlky (a teď nemyslim vydělit dvěma, ale z 1234 udělat 12 a 34). Tu větší od té menší odečíst (nebo naopak a potom dostat absolutní hodnotu z toho)) a dělat to do té doby, než nedostaneme potřebnou délku hashe ?

[kulik]

To netusim, zda by to bylo lepsi, nikde se neuvadi, k cemu to ma slouzit. Taky se to muze prevest do dvacitkove soustavy a pouzivat misto cislic pismena abecedy, to snad uz kazdeho napadne, co se s cislem da vsechno delat. Samozrejme pokud to ma byt nejak super bezpecne, tak by se mel pouzit nejaky salt apod., ale to z dotazu nevyplyva.

[retroslava]

Příloha:

• Hash.java (802 bytů)

Tak jsem ti něco malýho napsal, protože jsem se nudil. Koukni na to. Jinak by to měl bejt jednosměrnej algoritmus (neměla by se dát napsát funkce, která z čísla udělá string).

public static double getHash(String s, int lenght) {
        Double tmp = new Double(0);
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            int j = (int) c;
            tmp += j;
        }

        while (tmp < Math.pow(10, lenght - 1) || tmp > Math.pow(10, lenght)) {
            if (tmp >= Math.pow(10, lenght)) {
                //System.out.println("vetší než " + Math.pow(10, lenght));
                double zbytek = tmp % 2;
                tmp = ((tmp / 2) + zbytek)- (zbytek / 2);
            }
            if (tmp < Math.pow(10, lenght-1)) {
                //System.out.println("menší než " + Math.pow(10, lenght-1));
                tmp = tmp * 2;
            }
        }
        return tmp;
    }

[kuka]

No tohle je myslim tak trochu odstrasujici priklad, jak podobnou vec neimplementovat. Proc je napriklad promenna tmp Double a ne double? Proc ten hash neni celociselny?

[retroslava]

No tohle je myslim tak trochu odstrasujici priklad, jak podobnou vec neimplementovat

Je to čístě nástřel. Zajímala by mne vaše implementace, když tahle je odstrašující.

Proc je napriklad promenna tmp Double a ne double?

S tim Double máte pravdu, to jsem tam nechal omylem (předtím jsem to tam měl úmyslně).

Proc ten hash neni celociselny?

Hash je celočíselný, ale typu double. Snad napsat return (int)tmp; a přepsat předpis metody dotazující zvládne.

Jenom teď ještě řeším,že pro podobné stringy to hází dost podobné hashe. Ještě pošlu druhou verzi, kde bude tohle ošetřeno.

[retroslava]

Příloha:

• Hash.java (764 bytů)

Tak prosim, teď už to hází pro podobné odlišné "hashe". Můžete hodnodit pane Kuka. Vaše postřehy jsem vzal na vědomí a opravil.

public static int getHash(String s, int lenght) {
        int usedLenght = lenght + 1;
        double tmp = 0;
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            int j = (int) c;
            tmp += j;
        }

        tmp = Math.abs(Integer.reverse((int)tmp));

        while (tmp < Math.pow(10, usedLenght - 1) || tmp > Math.pow(10, usedLenght)) {
            if (tmp >= Math.pow(10, usedLenght)) {
                int zbytek = (int)(tmp % 2);
                tmp = ((tmp / 2) + zbytek) - (zbytek / 2);
            }
            if (tmp < Math.pow(10, usedLenght - 1)) {
                tmp = tmp * 2;
            }
        }
        
        return (int) (tmp / 10.0);
    }

[kuka]

Proc vymyslet kolo. Existuji ruzna doporuceni, jak pocitat haskody retezcu tak, aby mely pokud mozno pekne vlastnosti (napriklad aby prehozeni pismen vedlo na ruzny haskod, coz trivialni scitani znaku nesplnuje) - podivej se treba, jak se pocita hashcode pro tridu String, zdrojaky jsou napriklad pro Sun implementaci k dispozici. Realizovat celociselne operace v typech s plovouci carkou samozrejme ciste technicky lze (dokud nejsou cisla moc velka), ja to ale povazuji za spatny programatorsky postup, protoze to neni logicke.

[retroslava]

Přílohy:

• Hash.java (1017 bytů)
• srovnani.jpg (0 bytů)

Proc vymyslet kolo.

Na 100% souhlasim. Já tu metodu vymýšlim čístě ze zvědavosti.

prehozeni pismen vedlo na ruzny haskod, coz trivialni scitani znaku nesplnuje

Po malé úpravě (viz. příloha) splňuje. Ale trochu se stydím, že mě to nenapdalo hned (a hlavně samo od sebe).

Realizovat celociselne operace v typech s plovouci carkou samozrejme ciste technicky lze (dokud nejsou cisla moc velka), ja to ale povazuji za spatny programatorsky postup, protoze to neni logicke.

Javu se teprve učím. Normálně programuji v jazycích kde se datové typy moc neřeší (hlavně PHP). Upravil jsem metodu, aby celou dobu pracovala s celočíselnými datovým typem. Takhle vám to příjde logicky správné už ?

 

podivej se treba, jak se pocita hashcode pro tridu String, zdrojaky jsou napriklad pro Sun implementaci k dispozici

Kouknul jsem, implementoval jsem sám ze zvědavosti. Má to však pro zadání (pevná délka a asi by autor chtěl pouze kladná čísla) nějáké mouchy.

Jinak děkuji za poznámky. Rád se něco přiučím.

 

 

Jen pro srovnání, jsem změřil NetBeans profilerem rychlosti všech tří hashů (můj originální - getHash, moje implementace hashCode - hashCode a originální hashCode - origHashCode). Výsledky jsem přiložil jako obrázek.

 

 

public static long getHash(String s, int lenght) {
        int usedLenght = lenght + 1;
        long tmp = 0;
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            int j = (int) c;
            tmp += (j*(i+1));
        }

        tmp = Math.abs(Integer.reverse((int)tmp));

        while (tmp < Math.pow(10, usedLenght - 1) || tmp > Math.pow(10, usedLenght)) {
            if (tmp >= Math.pow(10, usedLenght)) {
                int zbytek = (int)(tmp % 2);
                tmp = ((tmp / 2) + zbytek) - (zbytek / 2);
            }
            if (tmp < Math.pow(10, usedLenght - 1)) {
                tmp = tmp * 2;
            }
        }
        
        return (tmp / 10);
    }

public static int hashCode(String s) {
        int hash = 0;

        for(int i =0; i < s.length(); i++) {
            hash = hash + s.charAt(i) * (int)Math.pow(31, s.length() - (i + 1));
        }

        return hash;
    }

[moira]

Můžu vědět, proč v tomto řádku odčítaš na konci tu nulu?

tmp = ((tmp / 2) + zbytek) - (zbytek / 2);

[retroslava]

Příloha:

• Hash.java (896 bytů)

Máte uplnou pravdu, je to zbytečné. Teď to opravdu postrádá smysl. Kód jsem opravil. V podstatě jsem došel sám ke stejnému výpočtu, jako je originální javovský String.hashCode. Rozdíl je skoro jen v tom, že já používám:

hash += s.charAt(i)*(i+1);

a originál Sun metoda hashCode:

hash += s.charAt(i) * (int)Math.pow(31, lenght - (i + 1));

[l4m4]

Toto je fakt ultrahnus. Nejhorší na celé věci je, že už komentář 2

http://www.abclinuxu.cz/poradna/programovani/show/285297#2

dává rozumný postup: prostě zkrátit nějaký známý hash dostupný jako knihovní funkce. Ale pán se nudí, a tak ignoruje dobré rady a bez jakékoli znalosti teorie hashovacích funkcí zbastlí jednu nefunkční pomocí výpočtů v polovoucí řádové čárce.

[retroslava]

Já se učim, a snažil jsem se vytknuté chyb opravit. Můžete ohodnotit poslední verzi ?

[Filip Jirsák]

Především je nesmysl pokoušet hashovací algoritmus jen tak vymyslet od prázdného stolu. Existuje dost popsaných hashovacích algoritmů, u kterých jsou známé jejich vlastnosti – stačí si mezi nimi nějaký vhodný vybrat a ten implementovat. Když budete vymýšlet nějaký algoritmus sám, nejspíš dojdete k něčemu, co bude jako hash fungovat špatně.

Můžete si to srovnat s algoritmy pro řazení. Když ho budete vymýšlet sám, uděláte nějaké řazení vkládáním nebo přinejlepším probublávání, quicksort hned nevymyslí každý. Pro hashovací nebo šifrovací funkce to platí ještě mnohonásobně víc.

[retroslava]

Jak už jsem psal. Souhlasím že je 100% nesmysl "znovu vynalézat kolo". Jen jsem po přečtení dotazu dostal chuť si to vyzkoušet. Jak jsem psal, s Javou začínám (ve škole). Každá příležitost něco udělat a nechat si to okomentovat někým, kdo javu umí (u nás ve škole to snad pořádně neumí ani ten cvičící), je pro mne cenná.

[Filip Jirsák]

Ale co jste si chtěl vyzkoušet? Napsat nějaký kód, který dělá bůhvíco, nebo napsat hashovací funkci? Pokud ten druhý případ, stejně potřebujete najít nějaké hashovací algoritmy, které pak budete implementovat. Programování neznamená, že budete hlava nehlava psát nějaký kód; umět najít správný algoritmus nebo už existující kód je stejně důležité.

[retroslava]

Příloha:

• Hash.java (890 bytů)

Ještě jsem opravil poslední chybičku (snad už) a opravdu teď nevím, proč můj algoritmus nevyhovuje zadání. Opravdu nejde o implementaci dokonalého hashování, jen o studentskou zvědavost (a opravdu to funguje). Používám téměř stejný hashovací algoritmus jako originální String.hashCode a došel jsem k němu sám, z toho mám radost. Pro nic víc jsem se nesnažil.

[Filip Jirsák]

Došel jste k něčemu sám, a vůbec netušíte k čemu, netušíte, jak se ten váš algoritmus chová. Váš algoritmus pouze převádí čísla z 2¹⁶ soustavy do desítkové soustavy modulo 2³². Proč tam je Long.reverse() nechápu vůbec. Váš algoritmus se od algoritmu použitého v Javě dost podstatně liší – ovšem je pravda, že ty algoritmy jsou co do míry hashování srovnatelné. Myslím, že pro oba dva nebude problém napsat inverzní funkci (která vrátí některý z možných vstupů), implementace String.hashCode() ve skutečnosti hashuje jenom podle pravých 7 znaků, další znaky se k hashi prakticky jen přičtou (takže u ASCII textu se osmý a další znak zprava promítnou jen do dolních 7 bitů hashe).

Pokud to celé má sloužit jako bezpečnostní kód, použil bych nějakou prověřenou hashovací funkci (SHA nebo klidně i MD5), výsledek bych rozdělil na skupiny bitů požadované délky a z těch bych XORováním udělal jednu skupinu požadované délky.

[retroslava]

Nemyslím se že je napsat funkci inverzní (k té mé) taková jednoduchá záležitost. Long.reverse() jsem tam zapojil, protože to hodně změní hashe pro podobné stringy. A máte pravdu, že podobné hashování bere pořádně v potaz jen x znaků (v mém případě zleva). Zkusím se zamyslet a vymyslet něco pořádnějšího, až bude trochu času. Mám se ještě co učit v tomhle oboru.

Jinak já osobně používám SHA s proměnou "solí" kde to jde (hesla a tak).

[Filip Jirsák]

To, že desítkové vyjádření vypadá „různě“, ještě nic neznamená. Tím, že otočíte pořadí bitů, hash skutečně nijak nevylepšíte – tedy za předpokladu, že jde o kvalitní hash, který bity vstupu distribuuje opravdu co nejvíce náhodně.

[retroslava]

Jo jo. Já už tuším kam celou dobu míříte. Máte pravdu. Díky za poučení, zkusim to víc nastudovat. Právě koukám na MD5. Ještě jednou díky za konstruktivní kritiku a užitečné informace, to dneska poskytne málokdo.