Indexkartläggning
Indexmappning (eller direkt adressering eller en trivial hashfunktion ) inom datavetenskap beskriver användningen av en array , där varje position motsvarar en nyckel i universum av möjliga värden. Tekniken är mest effektiv när universum av nycklar är ganska litet, så att det att tilldela en array med en position för varje möjlig nyckel. Dess effektivitet kommer från det faktum att en godtycklig position i en array kan undersökas i konstant tid .
Tillämpliga arrayer
Det finns många praktiska exempel på data vars giltiga värden är begränsade inom ett litet intervall. En trivial hash-funktion är ett lämpligt val när sådan data behöver fungera som en uppslagsnyckel. Några exempel inkluderar:
- månad på året (1–12)
- dag i månaden (1–31)
- veckodag (1–7)
- mänsklig ålder (0–130) – t.ex. livförsäkringsaktuarietabeller, tidsbundna bolån
- ASCII -tecken (0–127), som omfattar vanliga matematiska operatorsymboler, siffror, skiljetecken och engelska alfabetet
Exempel
Att använda en trivial hashfunktion, i en icke-iterativ tabelluppslagning, kan eliminera villkorlig testning och förgrening helt, vilket minskar instruktionsväglängden för ett datorprogram.
Undvik förgrening
Roger Sayle ger ett exempel på att eliminera en flervägsgren orsakad av en switch-sats :
inline bool HasOnly30Days ( int m ) { switch ( m ) { fall 4 : // April fall 6 : // Juni fall 9 : // September fall 11 : // November return true ; default : return false ; } }
Som kan ersättas med en tabelluppslagning:
0 0 0 0 0 0 0 0
inline bool HasOnly30Days ( int m ) { static const bool T [ ] = { , , , 1 , , 1 , , , 1 , , 1 , }; retur T [ m -1 ]; }