Inverser un hashCode

Bonjour

J'ai

Code:

---

1 2 3 4

String s = "toté"; int sr = s.hashCode(); System.out.println(sr);

---

Ce qui donne 3566256.

Peut-on inverser les choses.
Passer 3566256 et obtenir toté ?

Salut,


Non ce n'est pas possible.
Que veux-tu faire précisément ?


a++

Bonjour,

Non tu ne peux pas. C'est le principe d'une fonction hash, ce qu'elle n'est qu'à une seule direction (ou surjective pour reprendre le vocabulaire mathématique).

D'ailleurs tu peux théoriquement avoir plusieurs String qui auront pour hashCode 3566256. Et c'est logique puisque tu peux avoir beaucoup plus de String différentes que de valeurs de int en Java.

C'est pour un moteur de recherche.

Je dois stoker 3 valeurs.
Nom du texte
mot
valeur pondéral ( nb d'itération du mot cherchée / nb de mots d'un texte).

Dans mes bases, au lieu de stoker des string en trois colonne, ça donne
hashcode de : Nom du texte
hashcode de mot + valeur pondéral (>= 0 et < 1 (je vérifie que le texte n'est pas composé d'un même mot)).

Donc je stocke un int et un double sur 2 colonnes. Aussi rapide à indexer qu'avec des String mais 10 fois plus rapide dans les recherches.

Je voulais savoir si à partir des bases je pouvais retrouver les mots et faire des stat. par exemple.

Si tu as un index sur tes clefs, je pense que cela doit être aussi rapide avec les String.


a++

et n'oublie pas de gérer les colissions de tes hash. Le hash est un moyen très rapide de trouver dans quel coin se trouve la donnée, mais il faut y ajouter la string complete pour retirer toute ambiguité. On associe à un String un hashcode, mais a un hashcode on associe une Liste de strings!

Citation:

---

mais a un hashcode on associe une Liste de strings!

---

Et je suppose qu'on ne peux pas connaitre la liste de Strings.

Pour info, le moteur de recherche ne comporte "que" les 260 000 mots de la langue française. Les doublons sur si peu de mots doivent être rare.

Code:

---

1 2	System.out.println(Integer.MAX_VALUE); =2.147.483.647

---

Pour le moteur de recherche, il est en java, et la base de donnée, c'est hsqldb.
Du coup on peut l'exécuter sur différent OS, et la BD est intégrée.
Et pour que la DB reste de taille raisonnable, je préfère stoker des Int et Double, car ça prend moi de place.

Je voulais faire un truc petit, puissant et multi-plateforme.

Citation:

---

Envoyé par rockley

Pour info, le moteur de recherche ne comporte "que" les 260 000 mots de la langue française. Les doublons sur si peu de mots doivent être rare.

---

Et si tu as des doublons tu fais quoi ? Tu supprimes le mot de la langue française ???


a++

Citation:

---

Envoyé par rockley

Et je suppose qu'on ne peux pas connaitre la liste de Strings.

---

C'est à toi de la maintenir au fur et à mesure que tu génère tes hashcode.
Si tu veux chercher "rapidement" à partir des hashcode, il faudrait ceci dans ta DB:

Code:

---

id (unique), hashcode (indexé), nom (String), autres données dont tu as besoin

---

et mettre dans tes requetes

Code:

---

where hashcode=..... and nom=......

---

Maintenant, en général, quand tu indexe un colonne de type "string", la DB fait déjà ce genre d'optimisation pour toi :/

Citation:

---

Pour info, le moteur de recherche ne comporte "que" les 260 000 mots de la langue française. Les doublons sur si peu de mots doivent être rare.

---

Je te trouve extrèmement optimiste. En passant un dicitonnaire de ~230.000 mots ici, je trouve déjà 25 collisions (donc 50 mots à problème).

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

Map<Integer,String> existant = new HashMap<Integer, String>(); Map<Integer,Integer> collisions = new HashMap<Integer, Integer>(); Reader r = new InputStreamReader(new FileInputStream("/tmp/dico.txt"), "iso-8859-1"); BufferedReader br = new BufferedReader(r); String mot = null; int detected = 0; while ((mot = br.readLine())!=null) { int hash = mot.hashCode(); if (collisions.containsKey(hash)) { collisions.put(hash, collisions.get(hash)+1); System.out.printf("collision pour %s/%s: %X\n",mot,existant.get(hash),hash); detected++; } else collisions.put(hash, 0); existant.put(hash, mot); } System.out.println("Nombre de collisions détectées: "+detected);

---

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

collision pour affirme/affinée: BF1994E2 collision pour affirmes/affinées: 241907D1 collision pour confirme/confinée: DD6BF1A5 collision pour confirmes/confinées: D012436E collision pour démastiquerait/currys: AF9610CC collision pour es/aï: CAE collision pour esclaffées/afflouée: 24421F2D collision pour germent/gaîment: FB74DAB2 collision pour gym/gué: 191BB collision pour gyms/gués: 30A618 collision pour hannetonneras/boudeur: 42C58A6 collision pour hibernèrent/civilisasse: C44755E1 collision pour lerche/laîche: BE0FFBE7 collision pour liserassions/dépareillé: A5026849 collision pour mesa/maïa: 3315E6 collision pour mesas/maïas: 62FA74D collision pour mess/maïs: 3315F8 collision pour outillerait/marchant: E48DCC4 collision pour parme/panée: 65819F9 collision pour relançassiez/pneumothorax: 72D1331E collision pour révolutionnons/esthétisée: 1F753C93 collision pour ses/saï: 1BC61 collision pour solidifié/développerait: AF60A0A8 collision pour surclasserait/bactéricide: E5EA2D57 collision pour visualisé/baffâtes: 8383C9BF Nombre de collisions détectées: 25

---

Citation:

---

Et pour que la DB reste de taille raisonnable, je préfère stoker des Int et Double, car ça prend moi de place.

---

Un dictionnaire de 260.000 mots, ca représente environ 6M dans la base de données, à tout casser. Le gain n'a pas de sens.

Merci pour votre aide.

C'est vrai que je pense que je me suis fait un peu emporté par mes rêves d'optimisation.
Et l'anecdote, c'est que j'ai poussé le vice jusqu'à mettre des ++i au lieu de i++ dans mes boucles, pour économiser une copie.

Citation:

---

Envoyé par rockley

C'est vrai que je pense que je me suis fait un peu emporté par mes rêves d'optimisation.
Et l'anecdote, c'est que j'ai poussé le vice jusqu'à mettre des ++i au lieu de i++ dans mes boucles, pour économiser une copie.

---

Franchement : Arrêtes de penser "optimisation" ! Sinon tu vas finir par faire une usine à gaz illisible pour pas grand chose.


Tu gagnerais nettement plus à améliorer la lisibilité de ton code et son organisation.

Tant que tu n'as pas détecté des points morts dans ton code, il est inutile de vouloir optimisé. C'est même contre productif :(



a++

Citation:

---

Envoyé par rockley

j'ai poussé le vice jusqu'à mettre des ++i au lieu de i++ dans mes boucles, pour économiser une copie.

---

pour info c'est totalement inutile, la plupart des CPU faisant ces deux opérations en un seul cycle sur un registre :mouarf: