IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Langage Java Discussion :

Problème table hachage


Sujet :

Langage Java

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre averti
    Profil pro
    Inscrit en
    Octobre 2009
    Messages
    42
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2009
    Messages : 42
    Par défaut Problème table hachage
    Bonjour, voilà j'ai un fichier texte d'un poids d'environ 1Go et je dois construire une table de hachage à partir de ce fichier, et le but est de retourner le nombre d'occurence d'un mot saisi.

    Je suis partie, sur le chaînage linéaire, mais en le modifiant à ma sauce.

    En fait le principe que j'ai :

    Une classe Entry qui contient la clé, la valeur et le nombre d'occurence.

    Et voilà ma fonction de hachage :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    public int fonctionHachage(String pChaine)
    {
    int cumulCodeASCII = 0;
     
    /* On fait le cumul du code ascii de chaque lettre du mot */
    for(int i = 0; i < pChaine.length(); i++)
    	cumulCodeASCII = cumulCodeASCII + (int)pChaine.charAt(i) * (int) Math.pow(42, i);
     
    /* Compression */
    return Math.abs(cumulCodeASCII) % this.tableauBucket.length;
    }
    Donc la fonction retourne l'indice du bucket dans lequel insérer le mot.

    De plus, dans mon programme, je tiens compte du facteur de charge, en fait dès que mon facteur de charge dépasse 0,7 j'augmente la taille de mon tableau (tableauBucket).
    Le problème c'est que, si jamais je dois réinsérer un mot déjà inséré, je ne vais pas tomber sur le même indice du bucket dans lequel le mot est déjà présent, vu que la taille du tableau augmente.

    Comment faire pour retourner le même indice pour un même mot quelque soit la taille du tableau ?

    Merci d'avance

  2. #2
    Expert éminent
    Avatar de adiGuba
    Homme Profil pro
    Développeur Java/Web
    Inscrit en
    Avril 2002
    Messages
    13 938
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur Java/Web
    Secteur : Transports

    Informations forums :
    Inscription : Avril 2002
    Messages : 13 938
    Billets dans le blog
    1
    Par défaut
    Salut,


    Par curiosité : que représentera cette table de hashage ? Pourquoi n'utilises-tu pas une Map ?


    a++

  3. #3
    Membre averti
    Profil pro
    Inscrit en
    Octobre 2009
    Messages
    42
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2009
    Messages : 42
    Par défaut
    Je dois implémenter une table de hachage

    Ensuite je dois lire mon fichier et remplir la table de hachage à partir de ce fichier.

  4. #4
    Modérateur

    Profil pro
    Inscrit en
    Septembre 2004
    Messages
    12 582
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2004
    Messages : 12 582
    Par défaut
    Ouais c'est un exercice, quoi.

    Avoir des indices vers la table, qui ne varient pas quand la taille de la table varie, c'est évidemment contradictoire. C'est impossible.

    Le principe c'est de ne pas se baser sur les indices, mais sur le hachage lui-même : le nombre obtenu avant de faire le modulo sur la taille de la table. Ce nombre-là, lui, est invariant.

    Explications dans les cours et tutoriels pour apprendre Java.
    N'oubliez pas de consulter les FAQ Java et les cours et tutoriels Java

  5. #5
    Membre averti
    Profil pro
    Inscrit en
    Octobre 2009
    Messages
    42
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2009
    Messages : 42
    Par défaut
    oui je sais qu'il est invariant le nombre avant le modulo sur la taille, mais je suis obliger de faire le modulo pour être sur que l'insertion se fait dans les limites du tableau, autrement je ne vois pas comment je pourrai faire

  6. #6
    Modérateur

    Profil pro
    Inscrit en
    Septembre 2004
    Messages
    12 582
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2004
    Messages : 12 582
    Par défaut
    C'est facile :
    - quand tu veux un invariant, tu prends le nombre invariant.
    - quand tu veux un indice sur la table de hachage, tu prends l'invariant modulo la taille de la table de hachage.
    N'oubliez pas de consulter les FAQ Java et les cours et tutoriels Java

Discussions similaires

  1. PowerDesigner problème table
    Par damien77 dans le forum PowerAMC
    Réponses: 1
    Dernier message: 14/04/2008, 00h52
  2. Problème Table fichier
    Par orditosh dans le forum WinDev
    Réponses: 7
    Dernier message: 25/02/2008, 10h55
  3. Problème table vide
    Par cjacquel dans le forum Requêtes et SQL.
    Réponses: 4
    Dernier message: 21/01/2008, 16h10
  4. Problème : table temporaire
    Par midotoon dans le forum Administration
    Réponses: 10
    Dernier message: 10/05/2007, 00h01
  5. [Débutant]Problème tables attachées
    Par wwUUcc dans le forum MS SQL Server
    Réponses: 4
    Dernier message: 30/08/2006, 11h54

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo