[java] Hashmap/table die tegen groeien kan

[Alarmnummer]

Ik moet voor een aantal objecten een aantal hashtable aanmaken en daarvan kan ik van te voren niet bepalen hoeveel elementen erin komen. Naarmate een hashmap gaat groeien kan het voorkomen dat er een rehash gedaan moet worden. En dit is natuurlijk gigantisch langzaam. Ik ben eigelijk op zoek naar een hash structuur die wat beter hiertegen kan.

[Alarmnummer]

Ik kan trouwens wel zien hoeveel elementen er maximaal inzitten, maar er zullen zeker heel veel elementen dubbel in zitten.

Ik had zelf al zitten denken aan een getal dat bijhoud hoeveel gemiddeld nou verschillend is en dan

size = gemiddelde*maxSize

[Tsjipmanz]

Jij hebt toch aan de RuG nog n jaartje informatica gedaan? Heb je toen niet het 3 kilo zware boek "An introduction to algorithms" besteld?

Daar staan vast legio datastructuren in die bruikbaar zijn.

[Alarmnummer]

Ik ben hier eerst op uitgekomen.. Scheelt wel wat maar kan niet zeggen dat ik er nou onderste boven van ben.

Zometeen eerst maat eens met -Xrunhprof aan de slag of iemand moet nog een betere oplossing hebben.

code:

/**
 * UsedSolutionList.java
 *
 * @author Peter Veentjer
 */

package com.jph.expertSysteem.inferenceEngine.goalDrivenNonMonotonic.model;

import java.util.*;

import com.jph.expertSysteem.inferenceEngine.goalDrivenNonMonotonic.model.consequent.*;
import com.jph.expertSysteem.inferenceEngine.goalDrivenNonMonotonic.model.solution.*;


public class SolutionList
{
    public static int _maxSolutionListSize = 0;
    public static int _maxAllAntecedentHashMapSize = 0;

    public static int _totalMaxSize = 1;
    public static int _totalEffectiveSize = 1;
    
    private ArrayList    list = new ArrayList();
    
    private int maxAllAntecedentsSize = 0;
    
    public SolutionList(){
    }
    
    public int size(){
        return list.size();
    }
    
    public Solution get(int index){
        return (Solution)list.get(index);
    }
    
    public void add(Solution solution){
        if(solution == null)
            throw new NullPointerException("solution can`t be null");
        
        //if(hashMap.get(solution.getCVAPair().getConsequent())!=null)
        //  return;
        
        if(list.contains(solution))
            return;
        
        list.add(solution);
        //hashMap.put(solution.getCVAPair().getConsequent(),solution);
        
        maxAllAntecedentsSize+=solution.getAllAntedents().size();
        
        if(list.size()>_maxSolutionListSize)
            _maxSolutionListSize = list.size();
    }
    
    
    public void clear(){
        list.clear();
        maxAllAntecedentsSize = 0;
    }
    
    
    public IdentityHashMap getAllAntecedents(){
        int expectedSize = (int)(1.1*_totalEffectiveSize*maxAllAntecedentsSize)/_totalMaxSize;
        
        IdentityHashMap hashMap = new IdentityHashMap(expectedSize);
    
        int length = list.size();
        Solution tempSolution = null;
    
        for(int k=0;k<length;k++){
            tempSolution = (Solution)list.get(k);
            hashMap.put(tempSolution.getCVAPair().getConsequent(),tempSolution);
            hashMap.putAll(tempSolution.getAllAntedents());
        }
        
        _totalMaxSize+=maxAllAntecedentsSize;
        _totalEffectiveSize+=hashMap.size();
        
        if(hashMap.size()>_maxAllAntecedentHashMapSize)
            _maxAllAntecedentHashMapSize = hashMap.size();
        
        return hashMap;
    }
    
    
    public Solution[] getDirectAntecedents(){
        return (Solution[])list.toArray(new Solution[list.size()]);
    }
}

en dit zijn een paar stats:
==================================================================================
SolutionCount :1
Total solutions :5022
Max SolutionSetStack size :399
Max SolutionList size :2
Max SolutionSet size :3
Max All antecedent Hashmap size :1711

Efective max hashmap ratio :81.2321028046899 %

Total equals consequent count :471407
Total equals consequent local count :466850
Total equals consequent global count:4557

Total Searches :5280
Total Cache hits :870
Percentage from cache: :16.477272727272727
Total time ms :2.164
==================================================================================

[Alarmnummer]

een zoekfout gevonden hij loopt te veel dingen te herberekenen...

==================================================================================
SolutionCount :1
Total solutions :12534
Max SolutionSetStack size :963
Max SolutionList size :2
Max SolutionSet size :3
Max All antecedent Hashmap size :4267

Efective max hashmap ratio :80.77595540187062 %

Total equals consequent count :2728382
Total equals consequent local count :2717003
Total equals consequent global count:11379

Total Searches :13188
Total Cache hits :2184
Percentage from cache: :16.560509554140125
Total time ms :15.202
==================================================================================

==================================================================================
SolutionCount :1
Total solutions :7989
Max SolutionSetStack size :957
Max SolutionList size :2
Max SolutionSet size :3
Max All antecedent Hashmap size :3131

Efective max hashmap ratio :89.44522602567577 %

Total equals consequent count :1915333
Total equals consequent local count :1907084
Total equals consequent global count:8249

Total Searches :8643
Total Cache hits :769
Percentage from cache: :8.897373597130626
Total time ms :4.707
==================================================================================

Scheelt een factor 3!!!!!

PS Dit is niet hetzelfde voorbeeld als hierboven..
die is nu:
==================================================================================
SolutionCount :1
Total solutions :4009
Max SolutionSetStack size :487
Max SolutionList size :2
Max SolutionSet size :3
Max All antecedent Hashmap size :1571

Efective max hashmap ratio :89.52669135579441 %

Total equals consequent count :496533
Total equals consequent local count :492399
Total equals consequent global count:4134

Total Searches :4333
Total Cache hits :384
Percentage from cache: :8.862220170782367
Total time ms :1.102
==================================================================================