Hachage _java _squelette

Bonjour,
J'aimerais fournir à un public débutant un exemple, ou plutôt une idée sur la déclaration d'une table de hachage sous java. Ainsi, ce dernier peut mettre un visage sur cette structure et se constituer un point de départ.
Il ne s'agit pas de fournir une implémentation de la structure mais présenter un squelette le plus simple possible puisque le public est débutant. J'ai décidé de ne pas utiliser les interfaces et du coup le polymorphisme.
Dans un premier temps, j'ai présenté une classe Paire associant une clé à une valeur. puis j'ai enchainé avec une classe Table_Hachage pour mettre en avant les méthodes dont on a besoin.
Que pensez vous de cette démarche d'initiation? n'hésitez pas à critiquer et me proposer un avis

classe Paire {

// Attributs
Int clé ;
Object valeur;

// Méthodes
………….

}

classe Table_Hachage {

// Attributs
Paire[] clé_valeur;
// Méthodes
………….

ajouter_clé() {
……………
}
supprimer_clé(){
……………
}
rechercher_clé() {
……………
}
hachage() {
……………
}
gestion_collisions() {
……………
}

……………

}

que

Code:

---

new HashMap()

---

est beaucoup plus court à écrire

Oui, je sais. Mais je voulais avant de leur fournir du tout fait, de leur montrer les méthodes mises en jeu et qu'on pourrait faire à sa sauce. En fait, je voulais d'abord leur montrer un aspect générale avant de leur annoncer que la bibliothèque java a prévu le coup. Mais c'est discutable!

Oui c'est une très bonne idée,
D'autant plus que beaucoup ne connaitrons même certainnement pas le principe du hashage et son utilisation dans Java.
Excellent pour faire un peu de théorie en plus.

Merci pour vos réponses.

Moi je pense que new HashMap() suffit à condition de les poser devant le problème avant avec un peu de théorie pure.

- Comment faire pour gagner du temps sur une iteration dans 100 000 éléments ?
- Imaginez un moyen d'itérer qu'a des endroits ou c'est possible de trouver ce qu'on cherche.

Ainsi tu pourras parler de la nécessité d'utiliser un algo de tri avant un algo de recherche et enchainer sur les hashmap :)

Tout d'abord merci pour ta réponse.

Citation:

---

- Comment faire pour gagner du temps sur une iteration dans 100 000 éléments ?

---

Il s'agit de débutants. Encore faut il qu'ils sachent la différence entre itération et boucle. J'aimerais faire le plus simple possible. Peut être que tu as raison; A VOIR! Pourrais tu proposer un moyen très simple de l'expliquer?

Citation:

---

- Imaginez un moyen d'itérer qu'a des endroits ou c'est possible de trouver ce qu'on cherche.

---

Le hachage est utilisé en cas ou on n'a pas besoin de données triées. Je ne vois pas comment la recherche peut être guidée en ciblant des endroits??

Citation:

---

Ainsi tu pourras parler de la nécessité d'utiliser un algo de tri avant un algo de recherche et enchainer sur les hashmap

---

Hachage et tri, pour moi, ne font pas bon ménage.

Peut être que j'ai tort???
_________________

Pourtant, le hachage c'est justement une façon de trier les éléments ...

Pas un tri au sens d'ordonner, mais un tri quand même. C'est le principe même du hachage : associer à un élément un entier, et placer (ou chercher) l'objet selon l'entier en question.

Bonjour,

Citation:

---

Pourtant, le hachage c'est justement une façon de trier les éléments ...

---

Heureusement qu'on peut trouver l'objet si on le recherche grâce à la fonction de hachage. Mais en aucun cas, il ne s'agit de TRIER. C'est plutôt PLACER des objets selon la valeur calculée à partir de leur clé d'où la nuance.

Citation:

---

Pas un tri au sens d'ordonner, mais un tri quand même. C'est le principe même du hachage : associer à un élément un entier, et placer (ou chercher) l'objet selon l'entier en question.

---

Ouiiii, Pour moi un tri est forcément lié à une relation d'ORDRE. Dans le cas du hachage, il est certain qu'il n'y en a pas.

Citation:

---

Pas un tri au sens d'ordonner, mais un tri quand même.

---

Je dirais plutôt :
Pas un tri au sens d'ordonner, mais un placement selon une fonction quand même.

Citation:

---

Envoyé par wafiwafi

Heureusement qu'on peut trouver l'objet si on le recherche grâce à la fonction de hachage. Mais en aucun cas, il ne s'agit de TRIER. C'est plutôt PLACER des objets selon la valeur calculée à partir de leur clé d'où la nuance.

---

Ils sont pourtant précisément triés ... selon la valeur de leur hashCode.

Citation:

---

Ouiiii, Pour moi un tri est forcément lié à une relation d'ORDRE. Dans le cas du hachage, il est certain qu'il n'y en a pas.

---

S'il y a relation d'ordre, alors on ne trie plus, on ordonne (*). Par ailleurs, le hachage permet une relation d'ordre (puisqu'on fait une injection dans IN).
(*) le français étant précis, il y a bien une différence entre trier et ordonner.

On peut trier selon un prédicat. On défini un agencement : http://www.larousse.fr/dictionnaires/francais/trier

Quoi qu'il en soit je ne pense pas qu'ici ce soit le débat, et même s'ils sont débutants ils sont là pour apprendre ;)

Citation:

---

(*) le français étant précis, il y a bien une différence entre trier et ordonner.

---

Bien sûr. Je n'ai jamais dis le contraire d'ailleurs, on peut trier selon un ordre.
Je m'explique:
Si je dois appliquer à la lettre la définition (sans abus d'utilisation), du mot trier, je trouverai par exemple: Répartir selon un critère; dans ce cas je ne peux que m'incliner.
Par contre, quand on raisonne sur les clés d'objets, on cherche toujours à établir un certain ordre (>, <,=). dans ce cas, et par abus, les deux mots triés et ordonnées se rejoignent. On peut aussi bien dire une liste trié qu'une liste ordonnée. Dans tous les articles que j'ai pu lire, les auteurs s'expriment par l'une ou par l'autre.

Peut être que j'ai tort de suivre le flot?

D'ailleurs, il revient souvent dans des articles qu'on précise :
Le hachage est adapté pour des clés qui n'ont pas besoin d'être tri (c'est un abus !!).
En tout cas, c'est mon avis et il est discutable.

Plus précisément, il est question de mettre sur le net un article sur la question pour des internautes débutants. Il ne s'agit même pas d'un contact direct; tu imagines la difficulté??

Citation:

---

On peut trier selon un prédicat. On défini un agencement : http://www.larousse.fr/dictionnaires/francais/trier

---

OUI, pas de problèmes.

Citation:

---

Quoi qu'il en soit je ne pense pas qu'ici ce soit le débat, et même s'ils sont débutants ils sont là pour apprendre

---

C'est un point important; non? il est certain qu'il ne faut pas non plus s'y attarder.

Merci pour vos réponses.

Oui le français est précis nous le violons régulièrement.

Les développeurs confirmés irons directement aux sources pour comprendre car ils ont acquis une gymnastique d'esprit qui leur permettent de mieux comprendre le java que le français car moins riche et moins compliqué.

Pour tes débutants je pense que tu devrais peut être préférer un bon schéma qu'une implémentation :)

Tout dépend de tes objectifs. Si tu veux faire une introduction aux collections et que tu parles également des HashMap, alors implémenter ta version simplifié de HashMap est inutile et ne fera que les embrouiller. Si tu veux faire un cours d'algorithmique alors c'est peut-être pas une mauvaise chose, mais un bon schéma serait pas mal non plus en intro :)

Entièrement d'accord.
Merci pour ta vision objective sur la question.
J'en prends précieusement note.

Cela dit, pour des débutants, il ne me semble pas inutile, à défaut de refaire l'implémentation, d'expliquer comment ça marche (quelques schémas aident bien, en effet). En particulier, ça peut permettre de fixer la notion du hashCode et du equals, et l'importance des contrats qui sont derrière. Et puis ça lance naturellement le concept de polymorphisme :ccool:

On peut polymorpher à base de Arrays s'il faut même si c'est moins sexy :aie:

Oui, pourquoi pas!!