| dbpprop:abstract
|
- In computer science, a hash table or hash map is a data structure that uses a hash function to efficiently map certain identifiers or keys (e.g. , person names) to associated values (e.g. , their telephone numbers). The hash function is used to transform the key into the index (the hash) of an array element (the slot or bucket) where the corresponding value is to be sought. Ideally the hash function should map each possible key to a different slot index, but this ideal is rarely achievable in practice (unless the hash keys are fixed; i.e. new entries are never added to the table after creation). Most hash table designs assume that hash collisions — pairs of different keys with the same hash values — are normal occurrences and must be accommodated in some way. In a well-dimensioned hash table, the average cost for each lookup is independent of the number of elements stored in the table. Many hash table designs also allow arbitrary insertions and deletions of key-value pairs, at constant average (indeed, amortized
- In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen stehen dabei in Konkurrenz zu Baumstrukturen (wie etwa ein B*-Baum) und der Skip-List, die ebenfalls als Indexstruktur dienen können. Beim Einsatz einer Hashtabelle zur Suche in Datenmengen spricht man auch von einem Hashverfahren oder Streuspeicherverfahren.
- Hašovací tabulka (popřípadě hashovací tabulka nebo hešovací tabulka) je datová struktura, která asociuje hašovací klíče s odpovídajícími hodnotami. Hodnota klíče je spočtena z obsahu položky podle takového pravidla, aby klíč byl co nejjednoznačněji určen, tj. aby pravděpodobnost přiřazení stejného klíče dvěma a více rozdílným položkám byla co nejnižší a aby rozptyl hodnot klíčů pro dvě obsahově blízké položky byl co nejvyšší. Využití je např. pro rychlé vyhledávání položky v poli nebo v jiném homogenním datovém typu. Pomocí hašovací funkce přiřazujeme hodnotě klíče index (ukazatel) do homogenní datové struktury. Při zápisu obsahu položky zapíšeme položku na odpovídající místo. Pokud je obsazeno, pak pomocí vhodného algoritmu přiřadíme pro položku další volný index. Při vyhledávání položky spočteme s pomocí klíče index hledané položky. Pokud již bylo odpovídající místo přepsáno položkou s jiným klíčem, opět podle vhodného algoritmu prohledáváme další položky. Při správně zvolené velikosti (počtu položek) homogenní datové struktury a vhodně zvolené hašovací funkci má tento algoritmus složitost zdola omezenou na O(1).
- Una tabla hash o mapa hash es una estructura de datos que asocia llaves o claves con valores. La operación principal que soporta de manera eficiente es la búsqueda: permite el acceso a los elementos (teléfono y dirección, por ejemplo) almacenados a partir de una clave generada (usando el nombre o número de cuenta, por ejemplo). Funciona transformando la clave con una función hash en un hash, un número que la tabla hash utiliza para localizar el valor deseado. Las tablas hash se suelen implementar sobre arrays de una dimensión, aunque se pueden hacer implementaciones multi-dimensionales basadas en varias claves. Como en el caso de los arrays, las tablas hash proveen tiempo constante de búsqueda promedio O(1), sin importar el número de elementos en la tabla. Sin embargo, en casos particularmente malos el tiempo de búsqueda puede llegar a O(n), es decir, en función del número de elementos. Comparada con otras estructuras de arrays asociadas, las tablas hash son más útiles cuando se almacenan grandes cantidades de información. Las tablas hash almacenan la información en posiciones pseudo-aleatorias, así que el acceso ordenado a su contenido es bastante lento. Otras estructuras como árboles binarios auto-balanceables son más rápidos en promedio (tiempo de búsqueda O) pero la información está ordenada en todo momento.
- Tietojenkäsittelytieteessä hajautustaulu on hakurakenne eli avaimia arvoihin yhdistävä tietorakenne. Kun hajautustaululle annetaan avain (esimerkiksi henkilön nimi), se kertoo arvon (puhelinnumero). Sisäisesti se käyttää avaimesta hajautusfunktion avulla muodostettua tiivistelukua taulukon indeksinä. Siten haku toimii hyvin tehokkaasti, mutta alkioiden järjestykseen liittyvät operaatiot kuten suurimman arvon etsiminen eivät. Tyypillisesti hajautustaulua käytetään, kun halutaan indeksoida taulukkoa merkkijonoilla kokonaislukujen sijasta.
- En informatique, une table de hachage est une structure de données qui permet une association clé-élément, c'est-à-dire une implémentation du type abstrait table de symboles. On accède à chaque élément de la table via sa clé. Il s'agit d'un tableau ne comportant pas d'ordre (un tableau est indexé par des entiers). L'accès à un élément se fait en transformant la clé en une valeur de hachage (ou simplement hachage) par l'intermédiaire d'une fonction de hachage. Le hachage est un nombre qui permet la localisation des éléments dans le tableau, typiquement le hachage est l'index de l'élément dans le tableau. Une case dans le tableau est appelée alvéole. Tout comme les tableaux, les tables de hachage permettent un accès en O(1) en moyenne, quel que soit le nombre d'éléments dans la table. Toutefois le temps d'accès dans le pire des cas peut être de O(n). Comparées aux autres tableaux associatifs, les tables de hachage sont surtout utiles lorsque le nombre d'entrées est très important. La position des éléments dans une table de hachage est pseudo-aléatoire. Cette structure n'est donc pas adaptée pour accéder à des données triées. Des types de structures de données comme les arbres équilibrés sont généralement plus lents et sont plus complexes à implémenter mais maintiennent une structure ordonnée. Le fait de créer un hash à partir d'une clé peut engendrer un problème de collision, c’est-à-dire qu'à partir de deux clés différentes, la fonction de hachage pourrait renvoyer la même valeur de hash, et donc par conséquent donner accès à la même position dans le "tableau". Pour minimiser les risques de collisions, il faut donc choisir soigneusement sa fonction de hachage.
- In informatica una hash table, detta anche hash map, in italiano Tabella Hash è una struttura dati usata per mettere in corrispondenza una data chiave con un dato valore. Viene usata per l'implementazione di strutture dati astratte associative come Map o Set. Può usare qualsiasi tipo di dato come indice e tutte le operazioni si possono fare in tempo circa costante T(n) =. L'hash table è molto utilizzata nei metodi di ricerca nominati Hashing. L'hashing è un'estensione della ricerca indicizzata da chiavi che gestisce problemi di ricerca nei quali le chiavi di ricerca non presentano queste proprietà. Una ricerca basata su hashing è completamente diversa da una basata su confronti: invece che muoversi nella struttura data in funzione dell'esito dei confronti tra chiavi, si cerca di accedere agli elementi nella tabella in modo diretto tramite operazioni aritmetiche che trasformano le chiavi in indirizzi della tabella. Esistono vari tipi di algoritmi di hashing. L'hashing è un problema classico dell'informatica; molti algoritmi sono stati proposti, studiati a fondo e impiegati in pratica. Due metodi molto diffusi sono l'hashing statico e l'hashing estendibile e lineare, metodi utilizzati anche dai programmi DBMS.
- ファイル:HASHTB08. svg ハッシュテーブルの例(名前をキーとして電話番号を検索) ハッシュテーブル (hash table) は、キーと値の組（エントリと呼ぶ）を複数個格納し、キーに対応する値をすばやく参照するためのデータ構造。ハッシュ表ともいう。ハッシュテーブルは連想配列や集合の最も効率的な実装のうち1つである。
- Een hashtabel of hashmap zoals gebruikt in de informatica is een datastructuur waarbij sleutels worden geassocieerd met waardes. Dit wordt primair gebruikt voor een zoekoperatie waar men, voor een gegeven sleutel, bijvoorbeeld een naam, een bijbehorende waarde wil weten, bijvoorbeeld de woonplaats. Hashtabellen worden zeer vaak gebruikt in een configuratiebestand. De werking van een hashtabel berust op een hashfunctie die de sleutel omzet in een hashwaarde die gebruikt wordt om de (sleutel,waarde)-combinatie efficiënt te vinden. Gemiddeld genomen levert een hashtabel de gezochte waarde in een constante tijd, O(1), net zoals voor een normale array maar in uitzonderlijke gevallen kan de tijd evenredig zijn met het aantal elementen in de hashtabel O(n). Door de tijd die benodigd is voor het berekenen van de hashwaarde en het uiteindelijk vinden van de combinatie is een hashtabel het meest geschikt voor gevallen waarbij een groot aantal combinaties worden gebruikt. De onderliggende werking berust erop dat de sleutels worden omgezet in een semi-willekeurig getal, de hashwaarde, in een bepaald bereik. Als een combinatie moet worden opgezocht, wordt deze hashwaarde gebruikt als index in een lineaire tabel en gekeken of de waarde op de plek van de index overeenkomt met de sleutel. Is dit het geval, dan kan de waarde worden teruggegeven, O(1). Is dit niet het geval dan moet worden nagegaan of niet toevallig meerdere sleutels bestaan met de huidige waarde waardoor de sleutel niet op de index te vinden is maar op een alternative plek, bijvoorbeeld de volgende index of in een gelinkte lijst achter de eerst gevonden index of dat de gezochte sleutel in zijn geheel niet aanwezig is in de hashtabel. Een nadeel van een hashtabel is dat de sleutels eigenlijk willekeurig verdeeld staan in het geheugen. Als toegang tot de sleutels in een bepaalde volgorde nodig is, is dit waarschijnlijk niet de efficiëntste oplossing. In dat geval zou bijvoorbeeld een gebalanceerde binaire boom een betere oplossing kunnen zijn. Hashtabellen worden in allerlei soorten programma's gebruikt. De meeste programmeertalen bieden ondersteuning voor hashtabellen aan in hun standaard bibliotheken; voor C is er bijvoorbeeld GNU GLib. De meeste scripttalen ondersteunen hashtabellen met een speciale syntaxis. In deze talen worden hashtabellen ook wel veelvoudig gebruikt als datastructuren waarbij ze soms structuren en arrays vervangen.
- Hashtabell er en av datafagets viktigste datastrukturer. Istedet for å lete gjennom en serie, som kan ta O(N) i verste fall, eller en sortert liste på O(log N) tid, vil letetiden i en hashtabell være konstant, O(1). Leting etter et objekt iverksettes på basis av en nøkkel x, som klienten oppgir. Nøkkelen kan være et tall eller en tekst. Plassen beregnes så til k=h(x), der h(x) er hashfunksjonen som da skal være utført på O(1) tid. Objektet kan da hentes ut fra plass k, som er en av de N plassene til rådighet. En hashtabell kalles således assosiativ tabell, da den assosierer (kobler) nøkkel og verdi . Lagerstedet er vanligvis en tabell i maskinens hurtigminne, der man har O(1) tilgang til alle plassene. Man har den senere tid utviklet distribuert hashtabell som sprer lagringen på en eller flere maskiner for å øke pålitelighet og ytelse. Lageret vil til enhver tid ha en lastfaktor på B/N, der B er antall belagte plasser. Hvis flere nøkler kobles til samme plass oppstår kollisjon. Hashfunksjonen er laget for å unngå kollisjoner, men ved kollisjon må objektet lagres et annet sted, for eksempel i ekstra datastrukturer (trær, lister, såkalt «chaining»). En alternativ teknikk er å ta i bruk neste ledige lagerplass (lineær prøving), eventuelt lete seg eksponensielt frem til et ledig sted (kvadratisk prøving); en tredje teknikk er tilfeldig prøving, der man seriekobler flere hashfunksjoner for å beregne stedet. Dette øker tiden for å beregne h(x), men er da ment å redusere antall kollisjoner, og derigjennom gi redusert letetid. Sjansen for kollisjon øker med lastfaktor. Man kan da øke lagerplassen (N), etterfulgt av «rehashing», der objektene plasseres på det som vil være nytt korrekt sted. Dette er en O(N) operasjon. Eksempler på hashfunksjon er h(x) = x MOD N (der nøkkel er et heltall). Hvis nøkkelen er en tekst (eksempelvis en abonnents navn, som i figuren) kan h(x) være beregnet ut fra summen av et utvalg av tekstens tegn. Målet vil alltid være å unngå kollisjon, i hovedsak, ved å spre bruken jevnt over tabellen.
- W informatyce tablica mieszająca lub tablica haszująca to jeden ze sposobów realizacji tablicy asocjacyjnej, tj. struktury danych służącej do przechowywania informacji, w taki sposób aby możliwy był do nich szybki dostęp. Odwołania do przechowywanych obiektów dokonywane są na podstawie klucza, który dany obiekt (informację) identyfikuje. Kluczem może być na przykład ciąg znaków zawierający nazwisko pracownika, a wyszukiwaną informacją jego adres domowy.
- Em ciência da computação, uma tabela de dispersão (também conhecida por tabela de espalhamento ou tabela hash, do inglês hash) é uma estrutura de dados especial, que associa chaves de pesquisa a valores. Seu objetivo é, a partir de uma chave simples, fazer uma busca rápida e obter o valor desejado. É algumas vezes traduzida como tabela de escrutínio.
- В программировании хеш-таблица — это структура данных, реализующая интерфейс ассоциативного массива, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу. Существует два варианта хеш-таблиц: с прямой и открытой адресацией. Хеш-таблица содержит некоторый массив <math>H</math>, элементы которого есть пары (хеш-таблица с открытой адресацией) или списки пар (хеш-таблица с прямой адресацией). Выполнение операции в хеш-таблице начинается с вычисления хеш-функции от ключа. Получающееся хеш-значение <math>i = \mbox{hash(key)</math> играет роль индекса в массиве <math>H</math>. Затем выполняемая операция (добавление, удаление или поиск) перенаправляется объекту, который хранится в соответствующей ячейке массива <math>H[i]</math>. Ситуация, когда для различных ключей получается одно и то же хеш-значение, называется коллизией. Число хранимых элементов делённое на размер массива <math>H</math> (число возможных значений хеш-функции) называется коэффициентом заполнения хеш-таблицы (load factor) и является важным параметром, от которого зависит среднее время выполнения операций.
- En hashtabell är en tabell där data sparas tillsammans med en nyckel. Positionen i tabellen beräknas av en hashfunktion.
- 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
|
| rdfs:comment
|
- In computer science, a hash table or hash map is a data structure that uses a hash function to efficiently map certain identifiers or keys (e.g. , person names) to associated values (e.g. , their telephone numbers). The hash function is used to transform the key into the index (the hash) of an array element (the slot or bucket) where the corresponding value is to be sought.
- In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen stehen dabei in Konkurrenz zu Baumstrukturen (wie etwa ein B*-Baum) und der Skip-List, die ebenfalls als Indexstruktur dienen können.
- Hašovací tabulka (popřípadě hashovací tabulka nebo hešovací tabulka) je datová struktura, která asociuje hašovací klíče s odpovídajícími hodnotami. Hodnota klíče je spočtena z obsahu položky podle takového pravidla, aby klíč byl co nejjednoznačněji určen, tj. aby pravděpodobnost přiřazení stejného klíče dvěma a více rozdílným položkám byla co nejnižší a aby rozptyl hodnot klíčů pro dvě obsahově blízké položky byl co nejvyšší.
- Una tabla hash o mapa hash es una estructura de datos que asocia llaves o claves con valores. La operación principal que soporta de manera eficiente es la búsqueda: permite el acceso a los elementos (teléfono y dirección, por ejemplo) almacenados a partir de una clave generada (usando el nombre o número de cuenta, por ejemplo). Funciona transformando la clave con una función hash en un hash, un número que la tabla hash utiliza para localizar el valor deseado.
- Tietojenkäsittelytieteessä hajautustaulu on hakurakenne eli avaimia arvoihin yhdistävä tietorakenne. Kun hajautustaululle annetaan avain (esimerkiksi henkilön nimi), se kertoo arvon (puhelinnumero). Sisäisesti se käyttää avaimesta hajautusfunktion avulla muodostettua tiivistelukua taulukon indeksinä. Siten haku toimii hyvin tehokkaasti, mutta alkioiden järjestykseen liittyvät operaatiot kuten suurimman arvon etsiminen eivät.
- En informatique, une table de hachage est une structure de données qui permet une association clé-élément, c'est-à-dire une implémentation du type abstrait table de symboles. On accède à chaque élément de la table via sa clé. Il s'agit d'un tableau ne comportant pas d'ordre (un tableau est indexé par des entiers). L'accès à un élément se fait en transformant la clé en une valeur de hachage (ou simplement hachage) par l'intermédiaire d'une fonction de hachage.
- In informatica una hash table, detta anche hash map, in italiano Tabella Hash è una struttura dati usata per mettere in corrispondenza una data chiave con un dato valore. Viene usata per l'implementazione di strutture dati astratte associative come Map o Set. Può usare qualsiasi tipo di dato come indice e tutte le operazioni si possono fare in tempo circa costante T(n) =. L'hash table è molto utilizzata nei metodi di ricerca nominati Hashing.
- ファイル:HASHTB08. svg ハッシュテーブルの例(名前をキーとして電話番号を検索) ハッシュテーブル (hash table) は、キーと値の組（エントリと呼ぶ）を複数個格納し、キーに対応する値をすばやく参照するためのデータ構造。ハッシュ表ともいう。ハッシュテーブルは連想配列や集合の最も効率的な実装のうち1つである。
- Een hashtabel of hashmap zoals gebruikt in de informatica is een datastructuur waarbij sleutels worden geassocieerd met waardes. Dit wordt primair gebruikt voor een zoekoperatie waar men, voor een gegeven sleutel, bijvoorbeeld een naam, een bijbehorende waarde wil weten, bijvoorbeeld de woonplaats. Hashtabellen worden zeer vaak gebruikt in een configuratiebestand.
- Hashtabell er en av datafagets viktigste datastrukturer. Istedet for å lete gjennom en serie, som kan ta O(N) i verste fall, eller en sortert liste på O(log N) tid, vil letetiden i en hashtabell være konstant, O(1). Leting etter et objekt iverksettes på basis av en nøkkel x, som klienten oppgir. Nøkkelen kan være et tall eller en tekst. Plassen beregnes så til k=h(x), der h(x) er hashfunksjonen som da skal være utført på O(1) tid.
- W informatyce tablica mieszająca lub tablica haszująca to jeden ze sposobów realizacji tablicy asocjacyjnej, tj. struktury danych służącej do przechowywania informacji, w taki sposób aby możliwy był do nich szybki dostęp. Odwołania do przechowywanych obiektów dokonywane są na podstawie klucza, który dany obiekt (informację) identyfikuje. Kluczem może być na przykład ciąg znaków zawierający nazwisko pracownika, a wyszukiwaną informacją jego adres domowy.
- Em ciência da computação, uma tabela de dispersão (também conhecida por tabela de espalhamento ou tabela hash, do inglês hash) é uma estrutura de dados especial, que associa chaves de pesquisa a valores. Seu objetivo é, a partir de uma chave simples, fazer uma busca rápida e obter o valor desejado. É algumas vezes traduzida como tabela de escrutínio.
- В программировании хеш-таблица — это структура данных, реализующая интерфейс ассоциативного массива, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.
- En hashtabell är en tabell där data sparas tillsammans med en nyckel. Positionen i tabellen beräknas av en hashfunktion.
- 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
|
![[RDF Data]](/statics/sw-cube.png)
