Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Support
www.wp1.da-dk.nina.az
  • Wikipedia

For alternative betydninger se Tabel flertydig Se også artikler som begynder med Tabel En hashtabel er en datastruktur h

Hashtabel

Hashtabel
www.wp1.da-dk.nina.azhttps://www.wp1.da-dk.nina.az
image For alternative betydninger, se Tabel (flertydig). (Se også artikler, som begynder med Tabel)

En hashtabel er en datastruktur, hvor man hurtigt kan finde data ud fra en nøgle. Nøglen behandles med en hashfunktion, og resultatet bruges som indeks til selve opslaget.

Statisk hashtabel

I en statisk hashtabel er størrelsen af tabellen givet på forhånd. En enkel hashfunktion kunne være h(nøgle) = nøgle modulo tabellængden.

I tabellen gemmes tre ting i hver række. Nøglen, de tilhørende data og oplysninger om der er andre data, med den aktuelle hashværdi.

Eksempel

Et simpelt eksempel: Data gemmes i en tabel med plads til 11 poster. Det antages, at nøglen er et heltal. Hashfunktionen er h(nøgle) = nøgle modulo 11.

Hvis data med nøglerne 5, 14, 23, 32 og 42 indsættes, ser det sådan ud:

Index Nøgle Kollision 0 1 23 2 3 14 4 5 5 6 7 8 9 42 10 32 

Hvis der som i eksemplet ingen kollision er, kan data findes direkte. Det rigtige indeks kan beregnes entydigt ud fra nøglen. Kollisioner opstår, når to eller flere nøgler giver samme hash-værdi. Hvis der i tabellen ovenfor blev tilføjet data med nøglen 3, ville der opstå en kollision. Både h(14) og h(3) giver 3.

Kollisioner

Alt efter, hvordan hashtabellen er designet behandles kollisioner forskelligt. En mulighed er, at afsætte plads til de ekstra data, og så gennemsøge dette område sekventielt. Hvis der er plads til det, kan det registreres, hvilken adresse de kolliderende data befinder sig på:

Index Nøgle Kollision 0 1 23 2 3 14 11 4 5 5 6 7 8 9 42 10 32 -------------------- 11 3 12 13 14 15 

Da der også er et adressefelt i overløbsområdet, kan flere kollisioner på samme adresse håndteres så længe, der er plads.

Tidskompleksitet
Operation Relativ tid
Find O(1)
Indsæt O(1)
Slet O(1)

Kilder

  • File organization and Processing af Allan L. Tharp ISBN 0-471-61766-0
imageSpire
Denne artikel om datalogi eller et datalogi-relateret emne er en spire som bør udbygges. Du er velkommen til at hjælpe Wikipedia ved at udvide den.

wikipedia, dansk, wiki, bog, bøger, bibliotek, artikel, læs, download, gratis, gratis download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, billede, musik, sang, film, bog, spil, spil, mobile, Phone, Android, iOS, Apple, mobiltelefon, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, sonya, mi, PC, web, computer

Udgivelsesdato: April 10, 2025, 17:48 pm
De fleste læses
  • Kan 17, 2025

    Malariamyg

  • Kan 12, 2025

    Malangen

  • Kan 17, 2025

    Makroskopisk

  • Kan 08, 2025

    Major Grom: Tjumnoj Doktor

  • Kan 12, 2025

    Mainstream-økonomi

Daglige
  • Science fiction

  • Udenjordisk liv

  • Populærkultur

  • Ncuti Gatwa

  • Gazakrigen 2023-nu

  • Bukarest

  • Rumænien

  • Novo Nordisk

  • Lars Fruergaard Jørgensen

  • Zakarpatska oblast

NiNa.Az - Studio

  • Wikipedia

Tilmelding af nyhedsbrev

Ved at abonnere på vores mailingliste vil du altid modtage de seneste nyheder fra os.
Kom i kontakt
Kontakt os
DMCA Sitemap Feeds
© 2019 nina.az - Alle rettigheder forbeholdes.
Ophavsret: Dadaş Mammedov
Top