Hash table (original) (raw)
Taula hash, en ciències de la computació, és una estructura de dades que implementa un tipus abstracte de dades que és un array associatiu, una estructura que mapeja claus a valors. Una taula de hash empra una funció hash per a calcular un índex que apunta a un array o taula, a partir de la qual es pot obtenir el valor buscat. Idealment, la funció hash assignarà a cada clau a un únic índex, però la majoria de taules hash empren una funció hash imperfecta, que poden causar col·lisions on la funció hash genera el mateix índex per a més d'una clau (cal gestionar aquesta excepció).
| Property | Value |
|---|---|
| dbo:abstract | Taula hash, en ciències de la computació, és una estructura de dades que implementa un tipus abstracte de dades que és un array associatiu, una estructura que mapeja claus a valors. Una taula de hash empra una funció hash per a calcular un índex que apunta a un array o taula, a partir de la qual es pot obtenir el valor buscat. Idealment, la funció hash assignarà a cada clau a un únic índex, però la majoria de taules hash empren una funció hash imperfecta, que poden causar col·lisions on la funció hash genera el mateix índex per a més d'una clau (cal gestionar aquesta excepció). (ca) Hašovací tabulka (popřípadě hashovací tabulka nebo hešovací tabulka) je , která asociuje hašovací klíče s odpovídajícími hodnotami. Hodnota klíče je spočtena z obsahu položky pomocí nějaké hašovací funkce. Obvykle požadujeme nebo se alespoň snažíme, aby výpočet funkce byl rychlý, vypočítané klíče byly náhodné a rovnoměrně rozdělené mezi indexy tabulky a aby podobné hodnoty měly vzdálené klíče[zdroj?!]. 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 stejné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 v průměrném (tj. očekávaném) případě shora omezenou na O(1). (cs) جدول التجزئة ويعرف أيضا بـ: (جدول هاش، جداول التقطيع، خريطة هاش، خريطة تقطيع، قاموس هاش، قاموس التقطيع) هو أحد بنى المعطيات في علم الحاسوب يملك خصائص المصفوفات الترابطية (associative array) ويمكن باستخدامه اسناد قيمة إلى مفتاح ما في ذاكرة الحاسب. والبحث عن قيم محددة بسرعة كبيرة مقارنة ببنى المعطيات الأخرى. يستعمل جدول التقطيع، تابع تقطيع يمكنه من حساب مكان القيمة في لائحة المفاتيح. في الحالة المثالية، يفترض بجدول التقطيع، ربط كل مفتاح بحجرة معينة، لكن في الواقع ذلك يجعل زمن البحث فيه عن القيم المتضاربة كبيراً جداً، لذلك تم إيجاد عدة حلول ونماذج لجداول التقطيع تم فيها افتراض وجود قيم متضاربة وتم تحسين زمن البحث فيها بشكل كبير. (ar) In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Sie wird verwendet, um Datenelemente in einer großen Datenmenge zu suchen bzw. aufzufinden (Hash- oder Streuspeicherverfahren). Gegenüber alternativen Index-Datenstrukturen wie Baumstrukturen (z. B. ein B+-Baum) oder Skip-Listen zeichnen sich Hashtabellen üblicherweise durch einen konstanten Zeitaufwand bei Einfüge- bzw. Entfernen-Operationen aus. (de) Στην επιστήμη υπολογιστών, ο Πίνακας Κατακερματισμού (Αγγλικά: Hash table) είναι μία δομή δεδομένων για την αποθήκευση συνόλων στοιχείων. Χαρακτηριστικό του πίνακα κατακερματισμού είναι ότι μπορεί να εκτελέσει σε σταθερό χρόνο, δηλαδή με Ο(1), τις λειτουργίες της εισαγωγής, αναζήτησης και διαγραφής στοιχείων. Η κατασκευή του βασίζεται στη δομή πίνακα και στον ορισμό μίας συνάρτησης κατακερματισμού. Η συνάρτηση αυτή ορίζει για κάθε στοιχείο που εισάγεται έναν "κωδικό" που καθορίζει με μοναδικό τρόπο την θέση αποθήκευσης του στοιχείου αυτού στον πίνακα. Η συνάρτηση κατακερματισμού δεν είναι ένα-προς-ένα δηλαδή, παρότι σε όλα τα στοιχεία που είναι ίσα αποδίδεται πάντα ο ίδιος κωδικός, μπορεί διαφορετικά στοιχεία να έχουν και πάλι τον ίδιο κωδικό, με άμεσο αποτέλεσμα, κατά την εισαγωγή τους, να πρέπει να καταλήξουν στην ίδια θέση του πίνακα. Τέτοιες περιπτώσεις ονομάζονται συγκρούσεις (Αγγλικά: collisions) και έχουν αναπτυχθεί διάφοροι τρόποι αντιμετώπισής τους, όπως η χρήση . Στην γλώσσα προγραμματισμού Java η κλάση που υλοποιεί τον πίνακα κατακερματισμού είναι η HashMap, ενώ μια παλαιότερη υλοποίησή του είναι η κλάση Hashtable. (el) Hakettabelo estas datumstrukturo, realiganta asocian tabelon uzante haketfunkcion. (eo) In computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found. During lookup, the key is hashed and the resulting hash indicates where the corresponding value is stored. Ideally, the hash function will assign each key to a unique bucket, but most hash table designs employ an imperfect hash function, which might cause hash collisions where the hash function generates the same index for more than one key. Such collisions are typically accommodated in some way. In a well-dimensioned hash table, the average time complexity 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 amortized constant average cost per operation. Hashing is an example of a space-time tradeoff. If memory is infinite, the entire key can be used directly as an index to locate its value with a single memory access. On the other hand, if infinite time is available, values can be stored without regard for their keys, and a binary search or linear search can be used to retrieve the element. In many situations, hash tables turn out to be on average more efficient than search trees or any other table lookup structure. For this reason, they are widely used in many kinds of computer software, particularly for associative arrays, database indexing, caches, and sets. (en) Une table de hachage est, en informatique, une structure de données qui permet une association clé–valeur, c'est-à-dire une implémentation du type abstrait tableau associatif.Son but principal est de permettre de retrouver une clé donnée très rapidement, en la cherchant à un emplacement de la table correspondant au résultat d'une fonction de hachage calculée en O(1). Cela constitue un gain de temps très important pour les grosses tables, lors d'une recherche ou d'un besoin d'accès aux données en utilisant la clé définie. Il s'agit d'un tableau ne comportant pas d'ordre (contrairement à un tableau ordinaire qui est indexé par des entiers).On accède à chaque valeur du tableau par sa clé, qui transformée par une fonction de hachage en une valeur de hachage (un nombre) indexe les éléments de la table, ces derniers étant appelés alvéoles (en anglais, buckets ou slots). Le fait de créer une valeur de hachage à partir d'une clé peut engendrer un problème de collision, c’est-à-dire que deux clés différentes, voire davantage, pourront se retrouver associées à la même valeur de hachage et donc à la même alvéole (les fonctions de hachage ne sont pas injectives). Pour diminuer les risques de collisions, il faut donc premièrement choisir avec soin sa fonction de hachage. Ensuite, un mécanisme de résolution des collisions sera à implémenter si nécessaire. Il faudra alors stocker dans les alvéoles la paire clé–valeur et pas uniquement la valeur, afin de pouvoir comparer la clé avec celle qui sera donnée en entrée. Tout comme les tableaux ordinaires, les tables de hachage permettent un accès en O(1) en moyenne, quel que soit le nombre de paires clé–valeur dans la table. Toutefois, comme plusieurs paires clé–valeur peuvent se trouver dans la même alvéole, 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 de paires clé–valeur est très important[réf. nécessaire]. La position des paires clé–valeur dans une table de hachage est pseudo-aléatoire mais dépend de la fonction de hachage choisie et des clés utilisées. Cette structure n'est donc pas adaptée au feuilletage (browsing) de données voisines. Des types de structures de données comme les arbres équilibrés, généralement plus lents (en O(log n)) et un peu plus complexes à implémenter, maintiennent une structure ordonnée. (fr) Una tabla hash, matriz asociativa, hashing, mapa hash, tabla de dispersión o tabla fragmentada es una estructura de datos que implementa el tipo de dato abstracto llamado . Esta 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 identifica la posición (casilla o cubeta) donde la tabla hash localiza el valor deseado. Las tablas hash se suelen implementar sobre vectores 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 tienen un tiempo promedio de búsqueda mayor (tiempo de búsqueda O(log n)), pero la información está ordenada en todo momento. (es) In informatica un'hash table, 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. È molto utilizzata nei metodi di ricerca nominati hashing ovvero 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 di 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. Per quanto affermato, in una tabella di hashing ben dimensionata il costo medio di ricerca di ogni elemento è indipendente dal numero di elementi. 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. (it) 해시 테이블(hash table), 해시 맵(hash map), 해시 표는 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. 해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다. (ko) Een hashtabel of hashmap zoals gebruikt in de informatica is een datastructuur waarbij sleutels worden geassocieerd met waardes. Het is een implementatie van een associatieve array. 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 vaak gebruikt voor de implementatie van configuratiebestanden. 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 met behulp van een hashfunctie 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 andere plaats, 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 verspreid staan in het geheugen: ongebruikte sleutels nemen ruimte in beslag tussen de gebruikte sleutels. 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 standaardbibliotheken; C++ biedt bijvoorbeeld (vanaf de versie C++11) de klasse unordered_map aan en Java de klasse HashMap. De meeste scripttalen ondersteunen hashtabellen met een speciale syntaxis (bijvoorbeeld Perl, Python, PHP en Ruby). In deze talen worden hashtabellen ook wel veelvoudig gebruikt als datastructuren waarbij ze soms structuren en arrays vervangen. (nl) ハッシュテーブル (英: hash table) は、キーと値の組（エントリと呼ぶ）を複数個格納し、キーに対応する値をすばやく参照するためのデータ構造。ハッシュ表ともいう。ハッシュテーブルは連想配列や集合の効率的な実装のうち1つである。 (ja) Inom datavetenskap är hashtabell en datastruktur där data sparas tillsammans med en nyckel. Positionen i strukturen beräknas med en hashfunktion. Ofta behöver man en datastruktur som kan hantera både insättningar och sökningar effektivt. Då fungerar varken vektorer eller länkade listor, detta eftersom: * Sökning i en osorterad vektor tar linjär tid; * i en sorterad vektor kan man använda binärsökning som är mycket effektiv, men då tar istället insättningarna linjär tid; * i en länkad lista kan man göra insättningar på konstant tid, men sökningen blir linjär. (sv) Tablica mieszająca lub tablica z haszowaniem (ang. hash table, niekiedy błędnie tłumaczone jako „tablica haszująca”) – struktura danych, która jest jednym ze sposobów realizacji tablicy asocjacyjnej, tj. abstrakcyjnego typu danych służącego do przechowywania informacji w taki sposób, aby możliwy był do nich szybki dostęp. Tablica mieszająca umożliwia również szybkie porównywanie danych, np. fragmentów tekstów, plików. Odwołania do przechowywanych obiektów dokonywane są na podstawie klucza, który dany obiekt (informację) identyfikuje. (pl) 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. (pt) Геш-таблиця — структура даних, що реалізує інтерфейс асоціативного масиву, а саме, вона дозволяє зберігати пари (ключ, значення) і здійснювати три операції: операцію додавання нової пари, операцію пошуку і операцію видалення за ключем. (uk) Хеш-табли́ца — это структура данных, реализующая интерфейс ассоциативного массива, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию удаления и операцию поиска пары по ключу. (ru) 散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在記憶體儲存位置的数据结构。也就是说，它通过计算出一个键值的函数，将所需查询的数据映射到表中一个位置来讓人访问，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。 一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名到首字母的一个函数关系），在首字母为W的表中查找“王”姓的电话号码，显然比直接查找就要快得多。这里使用人名作为关键字，“取首字母”是这个例子中散列函数的函数法则，存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Hash_table_3_1_1_0_1_0_0_SP.svg?width=300 |
| dbo:wikiPageExternalLink | http://opendatastructures.org/versions/edition-0.1e/ods-java/5_Hash_Tables.html https://archive.org/details/datastructuresal00good_183 https://archive.org/details/datastructuresal00good_183/page/n368 http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-7-hashing-hash-functions/ http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-8-universal-hashing-perfect-hashing/ https://xlinux.nist.gov/dads/HTML/hashtab.html |
| dbo:wikiPageID | 13833 (xsd:integer) |
| dbo:wikiPageLength | 51530 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1124674828 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Power_of_two dbr:Probability_distribution dbr:Proportionality_(mathematics) dbr:Python_(programming_language) dbr:Ruby_(programming_language) dbr:Elaine_M._McGraw dbr:Pat_Morin dbr:Memory_management_(operating_systems) dbr:Key–value_pair dbr:Index_(database) dbr:Bitwise_operation dbr:Bloom_filter dbr:Pearson's_chi-squared_test dbr:Perfect_hash_function dbr:Cuckoo_hashing dbr:Variance dbr:Double_hashing dbr:Dynamic_array dbr:Dynamic_perfect_hashing dbr:Infinite_loop dbr:Invariant_(mathematics) dbr:Unique_key dbr:Pearson_hashing dbr:Worst-case_complexity dbr:Concurrent_computing dbr:Continuous_uniform_distribution dbr:Analysis_of_algorithms dbr:Memory_latency dbr:Generics_in_Java dbr:Low-discrepancy_sequence dbr:W._Wesley_Peterson dbr:Search_data_structure dbr:Gene_Amdahl dbr:Golden_ratio dbr:Modulo_operation dbr:NIST dbr:Concurrent_hash_table dbr:Consistent_hashing dbr:Open_addressing dbr:Optimal_binary_search_tree dbr:Andrey_Ershov dbr:Arnold_Dumey dbr:Lexicographic_order dbr:Linear_search dbr:Cache-oblivious_algorithm dbr:Cache_(computing) dbr:Cache_prefetching dbr:Cluster_analysis dbr:Command_pattern dbr:Computational_complexity_theory dbr:Computer_architecture dbr:Computer_memory dbr:Computing dbr:Hopscotch_hashing dbr:Memory_pool dbr:Page_(computer_memory) dbr:Translation_lookaside_buffer dbr:Standard_library dbr:B-tree dbr:C++11 dbr:CPU_cache dbr:Time_complexity dbr:Total_order dbr:Data_structure dbr:Database_index dbr:Fusion_tree dbr:Hash_array_mapped_trie dbr:Hash_collision dbr:Hash_function dbr:K-independent_hashing dbr:Lazy_deletion dbr:Linear_hashing dbr:Linear_probing dbr:Linked_list dbr:Locality_of_reference dbr:Abstract_data_type dbr:Academic_publishing dbr:Amortized_analysis dbr:DBM_(computing) dbr:Dynamic_memory_allocation dbr:Fragmentation_(computing) dbr:Bit_length dbr:Statistical_dispersion dbr:Memory_footprint dbr:Primitive_data_type dbc:Hashing dbr:Hans_Peter_Luhn dbr:JavaScript dbr:Java_(programming_language) dbr:Template_(C++) dbr:Prime_number dbr:Stable_hashing dbr:Static_Hashing dbr:Arthur_Samuel dbr:Assembly_language dbc:Articles_with_example_C_code dbr:Bit_array dbc:Hash_based_data_structures dbr:Coalesced_hashing dbr:Transposition_table dbr:Wrapper_function dbr:Disk_drive dbr:Distributed_hash_table dbr:Donald_Knuth dbr:Associative_array dbr:Average-case_complexity dbr:Mark-compact_algorithm dbr:IBM dbr:IBM_701 dbr:Injective_function dbr:Nathaniel_Rochester_(computer_scientist) dbr:Rabin–Karp_string_search_algorithm dbr:Real-time_system dbr:Real_number dbr:Sequence dbr:Word_(computer_architecture) dbr:Use_case dbr:Array_index dbr:Set_(abstract_data_type) dbr:Software dbr:Uniform_distribution_(discrete) dbr:Value_(computer_science) dbr:Euclidean_distance dbr:Extendible_hashing dbr:IBM_Research dbr:Space-time_tradeoff dbr:Universal_hashing dbr:NP-hardness dbr:Name–value_pair dbr:Quadratic_probing dbr:PhotoDNA dbr:Self-balancing_binary_search_tree dbr:Search_tree dbr:Set_data_structure dbr:Binary_search dbr:Spatial_locality dbr:Table_(computing) dbr:File:Hash_table_5_0_1_1_1_1_0_LL.svg dbr:File:Hash_table_5_0_1_1_1_1_0_SP.svg dbr:File:Hash_table_5_0_1_1_1_1_1_LL.svg dbr:File:Hash_table_average_insertion_time.png dbr:File:Hash_table_3_1_1_0_1_0_0_SP.svg |
| dbp:deleteAvg | Θ (en) |
| dbp:deleteWorst | O (en) |
| dbp:insertAvg | Θ (en) |
| dbp:insertWorst | O (en) |
| dbp:inventedYear | 1953 (xsd:integer) |
| dbp:name | Hash table (en) |
| dbp:searchAvg | Θ (en) |
| dbp:searchWorst | O (en) |
| dbp:spaceAvg | Θ (en) |
| dbp:spaceWorst | O (en) |
| dbp:type | Unordered associative array (en) |
| dbp:wikiPageUsesTemplate | dbt:! dbt:Authority_control dbt:Cite_book dbt:Cite_journal dbt:Commons_category dbt:Distinguish dbt:Div_col dbt:Div_col_end dbt:Main dbt:R dbt:Redirect dbt:Reflist dbt:Rp dbt:See_also dbt:Short_description dbt:Use_mdy_dates dbt:Wikibooks dbt:Data_structures dbt:Infobox_data_structure |
| dct:subject | dbc:Hashing dbc:Articles_with_example_C_code dbc:Hash_based_data_structures |
| gold:hypernym | dbr:Structure |
| rdf:type | owl:Thing yago:WikicatSearchAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Arrangement105726596 yago:Cognition100023271 yago:DataStructure105728493 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity dbo:Building yago:Rule105846932 yago:Structure105726345 yago:WikicatDataStructures |
| rdfs:comment | Taula hash, en ciències de la computació, és una estructura de dades que implementa un tipus abstracte de dades que és un array associatiu, una estructura que mapeja claus a valors. Una taula de hash empra una funció hash per a calcular un índex que apunta a un array o taula, a partir de la qual es pot obtenir el valor buscat. Idealment, la funció hash assignarà a cada clau a un únic índex, però la majoria de taules hash empren una funció hash imperfecta, que poden causar col·lisions on la funció hash genera el mateix índex per a més d'una clau (cal gestionar aquesta excepció). (ca) In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Sie wird verwendet, um Datenelemente in einer großen Datenmenge zu suchen bzw. aufzufinden (Hash- oder Streuspeicherverfahren). Gegenüber alternativen Index-Datenstrukturen wie Baumstrukturen (z. B. ein B+-Baum) oder Skip-Listen zeichnen sich Hashtabellen üblicherweise durch einen konstanten Zeitaufwand bei Einfüge- bzw. Entfernen-Operationen aus. (de) Hakettabelo estas datumstrukturo, realiganta asocian tabelon uzante haketfunkcion. (eo) 해시 테이블(hash table), 해시 맵(hash map), 해시 표는 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. 해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다. (ko) ハッシュテーブル (英: hash table) は、キーと値の組（エントリと呼ぶ）を複数個格納し、キーに対応する値をすばやく参照するためのデータ構造。ハッシュ表ともいう。ハッシュテーブルは連想配列や集合の効率的な実装のうち1つである。 (ja) Inom datavetenskap är hashtabell en datastruktur där data sparas tillsammans med en nyckel. Positionen i strukturen beräknas med en hashfunktion. Ofta behöver man en datastruktur som kan hantera både insättningar och sökningar effektivt. Då fungerar varken vektorer eller länkade listor, detta eftersom: * Sökning i en osorterad vektor tar linjär tid; * i en sorterad vektor kan man använda binärsökning som är mycket effektiv, men då tar istället insättningarna linjär tid; * i en länkad lista kan man göra insättningar på konstant tid, men sökningen blir linjär. (sv) Tablica mieszająca lub tablica z haszowaniem (ang. hash table, niekiedy błędnie tłumaczone jako „tablica haszująca”) – struktura danych, która jest jednym ze sposobów realizacji tablicy asocjacyjnej, tj. abstrakcyjnego typu danych służącego do przechowywania informacji w taki sposób, aby możliwy był do nich szybki dostęp. Tablica mieszająca umożliwia również szybkie porównywanie danych, np. fragmentów tekstów, plików. Odwołania do przechowywanych obiektów dokonywane są na podstawie klucza, który dany obiekt (informację) identyfikuje. (pl) 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. (pt) Геш-таблиця — структура даних, що реалізує інтерфейс асоціативного масиву, а саме, вона дозволяє зберігати пари (ключ, значення) і здійснювати три операції: операцію додавання нової пари, операцію пошуку і операцію видалення за ключем. (uk) Хеш-табли́ца — это структура данных, реализующая интерфейс ассоциативного массива, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию удаления и операцию поиска пары по ключу. (ru) 散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在記憶體儲存位置的数据结构。也就是说，它通过计算出一个键值的函数，将所需查询的数据映射到表中一个位置来讓人访问，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。 一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名到首字母的一个函数关系），在首字母为W的表中查找“王”姓的电话号码，显然比直接查找就要快得多。这里使用人名作为关键字，“取首字母”是这个例子中散列函数的函数法则，存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。 (zh) جدول التجزئة ويعرف أيضا بـ: (جدول هاش، جداول التقطيع، خريطة هاش، خريطة تقطيع، قاموس هاش، قاموس التقطيع) هو أحد بنى المعطيات في علم الحاسوب يملك خصائص المصفوفات الترابطية (associative array) ويمكن باستخدامه اسناد قيمة إلى مفتاح ما في ذاكرة الحاسب. والبحث عن قيم محددة بسرعة كبيرة مقارنة ببنى المعطيات الأخرى. يستعمل جدول التقطيع، تابع تقطيع يمكنه من حساب مكان القيمة في لائحة المفاتيح. (ar) Hašovací tabulka (popřípadě hashovací tabulka nebo hešovací tabulka) je , která asociuje hašovací klíče s odpovídajícími hodnotami. Hodnota klíče je spočtena z obsahu položky pomocí nějaké hašovací funkce. Obvykle požadujeme nebo se alespoň snažíme, aby výpočet funkce byl rychlý, vypočítané klíče byly náhodné a rovnoměrně rozdělené mezi indexy tabulky a aby podobné hodnoty měly vzdálené klíče[zdroj?!]. (cs) Στην επιστήμη υπολογιστών, ο Πίνακας Κατακερματισμού (Αγγλικά: Hash table) είναι μία δομή δεδομένων για την αποθήκευση συνόλων στοιχείων. Χαρακτηριστικό του πίνακα κατακερματισμού είναι ότι μπορεί να εκτελέσει σε σταθερό χρόνο, δηλαδή με Ο(1), τις λειτουργίες της εισαγωγής, αναζήτησης και διαγραφής στοιχείων. Στην γλώσσα προγραμματισμού Java η κλάση που υλοποιεί τον πίνακα κατακερματισμού είναι η HashMap, ενώ μια παλαιότερη υλοποίησή του είναι η κλάση Hashtable. (el) Una tabla hash, matriz asociativa, hashing, mapa hash, tabla de dispersión o tabla fragmentada es una estructura de datos que implementa el tipo de dato abstracto llamado . Esta 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 identifica la posición (casilla o cubeta) donde la tabla hash localiza el valor deseado. (es) In computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found. During lookup, the key is hashed and the resulting hash indicates where the corresponding value is stored. (en) Une table de hachage est, en informatique, une structure de données qui permet une association clé–valeur, c'est-à-dire une implémentation du type abstrait tableau associatif.Son but principal est de permettre de retrouver une clé donnée très rapidement, en la cherchant à un emplacement de la table correspondant au résultat d'une fonction de hachage calculée en O(1). Cela constitue un gain de temps très important pour les grosses tables, lors d'une recherche ou d'un besoin d'accès aux données en utilisant la clé définie. (fr) In informatica un'hash table, 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. (it) Een hashtabel of hashmap zoals gebruikt in de informatica is een datastructuur waarbij sleutels worden geassocieerd met waardes. Het is een implementatie van een associatieve array. 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 vaak gebruikt voor de implementatie van configuratiebestanden. (nl) |
| rdfs:label | جدول تجزئة (ar) Taula hash (ca) Hašovací tabulka (cs) Hashtabelle (de) Πίνακας κατακερματισμού (el) Hakettabelo (eo) Tabla hash (es) Hash table (en) Hash table (it) Table de hachage (fr) 해시 테이블 (ko) ハッシュテーブル (ja) Hashtabel (nl) Tablica mieszająca (pl) Хеш-таблица (ru) Tabela de dispersão (pt) Hashtabell (sv) 哈希表 (zh) Геш-таблиця (uk) |
| rdfs:seeAlso | dbr:2-choice_hashing |
| owl:differentFrom | dbr:Hash_list dbr:Hash_tree_(disambiguation) |
| owl:sameAs | dbpedia-pl:Hash table freebase:Hash table http://linked-web-apis.fit.cvut.cz/resource/binary_hashtable_format yago-res:Hash table http://d-nb.info/gnd/1046573225 wikidata:Hash table dbpedia-ar:Hash table dbpedia-bg:Hash table http://bs.dbpedia.org/resource/Hash_tabela dbpedia-ca:Hash table dbpedia-cs:Hash table dbpedia-da:Hash table dbpedia-de:Hash table dbpedia-el:Hash table dbpedia-eo:Hash table dbpedia-es:Hash table dbpedia-et:Hash table dbpedia-fa:Hash table dbpedia-fi:Hash table dbpedia-fr:Hash table dbpedia-he:Hash table http://hi.dbpedia.org/resource/हैश_टेबल dbpedia-hr:Hash table dbpedia-hu:Hash table dbpedia-it:Hash table dbpedia-ja:Hash table dbpedia-ko:Hash table dbpedia-lmo:Hash table http://lt.dbpedia.org/resource/Maišos_lentelė http://lv.dbpedia.org/resource/Jaucējtabula http://ml.dbpedia.org/resource/ഹാഷ്_ടേബിൾ http://mn.dbpedia.org/resource/Хэш_хүснэгт dbpedia-nl:Hash table dbpedia-nn:Hash table dbpedia-no:Hash table dbpedia-pt:Hash table dbpedia-ru:Hash table dbpedia-simple:Hash table dbpedia-sk:Hash table dbpedia-sr:Hash table dbpedia-sv:Hash table dbpedia-th:Hash table http://tl.dbpedia.org/resource/Tablang_hash dbpedia-tr:Hash table dbpedia-uk:Hash table dbpedia-vi:Hash table dbpedia-zh:Hash table https://global.dbpedia.org/id/ytgQ |
| prov:wasDerivedFrom | wikipedia-en:Hash_table?oldid=1124674828&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Hash_table_3_1_1_0_1_0_0_SP.svg wiki-commons:Special:FilePath/Hash_table_5_0_1_1_1_1_0_LL.svg wiki-commons:Special:FilePath/Hash_table_5_0_1_1_1_1_0_SP.svg wiki-commons:Special:FilePath/Hash_table_5_0_1_1_1_1_1_LL.svg wiki-commons:Special:FilePath/Hash_table_average_insertion_time.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Hash_table |
| is dbo:academicDiscipline of | dbr:Rasmus_Pagh |
| is dbo:wikiPageDisambiguates of | dbr:Hash |
| is dbo:wikiPageRedirects of | dbr:Collision_resolution_in_hash_tables dbr:Hash_Table dbr:Dynamic-sized_hash_table dbr:Hash_tables dbr:Scatter_storage dbr:Separate_chaining dbr:Load_factor_(computer_science) dbr:Chaining_hash_table dbr:Hash-Based_Indexes dbr:Hash-table dbr:Hash_map dbr:Hash_table_collision dbr:Hash_table_collisions dbr:Hashmap dbr:Hashtable dbr:Array_hash_table dbr:Open_hashing dbr:Direct_chaining dbr:Rehash dbr:Address-calculation_sort dbr:Collision_resolution_scheme dbr:External_chaining |
| is dbo:wikiPageWikiLink of | dbr:Ruby_(programming_language) dbr:Elaine_M._McGraw dbr:ElcomSoft dbr:Element_distinctness_problem dbr:Enumerated_type dbr:Enumeration_algorithm dbr:List_of_data_structures dbr:Merkle_tree dbr:Null-terminated_string dbr:BeRTOS dbr:Berkeley_DB dbr:Binary_search_algorithm dbr:Birthday_problem dbr:Bitcask dbr:Bloom_filter dbr:Anna_Karlin dbr:Best,_worst_and_average_case dbr:Pathological_(mathematics) dbr:Percent_sign dbr:Perfect_hash_function dbr:Persistent_data_structure dbr:Rexx dbr:Cuckoo_hashing dbr:Cycle_detection dbr:Van_Emde_Boas_tree dbr:Versant_Object_Database dbr:Vile_(text_editor) dbr:De_Bruijn_sequence dbr:Double_hashing dbr:Dynamic_perfect_hashing dbr:Index_mapping dbr:Indexed_file dbr:Indifference_graph dbr:Interpolation_search dbr:List_of_sequence_alignment_software dbr:Pearson_hashing dbr:Collision_resolution_in_hash_tables dbr:Common_Lisp dbr:Computer_algebra dbr:Count–min_sketch dbr:Cryptographic_hash_function dbr:Anatree dbr:Memcached dbr:SUHA_(computer_science) dbr:Generation_of_primes dbr:Genome_skimming dbr:Geometric_hashing dbr:Object-oriented_programming dbr:Very_large_database dbr:Search_data_structure dbr:Clojure dbr:Eiffel_(programming_language) dbr:Eiichi_Goto dbr:GLib dbr:GNU_Smalltalk dbr:Glossary_of_computer_science dbr:Go_(programming_language) dbr:Branch_table dbr:Name_collision dbr:Concurrent_hash_table dbr:Consistent_hashing dbr:Container_(abstract_data_type) dbr:Content-addressable_network dbr:Core_Foundation dbr:Critical_section dbr:Rolling_hash dbr:Open_addressing dbr:Apache_Portable_Runtime dbr:Array_(data_structure) dbr:Array_(data_type) dbr:Linear_search dbr:Lisp_(programming_language) dbr:Load_balancing_(computing) dbr:Lua_(programming_language) dbr:MIRC_scripting_language dbr:Cache-oblivious_algorithm dbr:Standard_Template_Library dbr:Claw_finding_problem dbr:Closest_pair_of_points_problem dbr:Collision_attack dbr:Comparison_of_programming_languages_(associative_array) dbr:Delone_set dbr:Feature_hashing dbr:Functional_programming dbr:Hopscotch_hashing dbr:Key–value_database dbr:Peer-to-peer dbr:Structure dbr:Table_(information) dbr:Ternary_search_tree dbr:Theoretical_computer_science dbr:Htab dbr:Standard_library dbr:C++11 dbr:C++_Technical_Report_1 dbr:C_shell dbr:Timeline_of_file_sharing dbr:TinyURL dbr:Tkrzw dbr:Trie dbr:Data_model dbr:Data_structure dbr:Database_engine dbr:Database_index dbr:Database_storage_structures dbr:Dataflow_programming dbr:Distance_oracle dbr:Distributed_operating_system dbr:Fusion_tree dbr:Collision_resolution dbr:HAT-trie dbr:HTree dbr:Hash_array_mapped_trie dbr:Hash_calendar dbr:Hash_collision dbr:Hash_consing dbr:Hash_function dbr:Hash_join dbr:Hash_list dbr:Hash_tree_(persistent_data_structure) dbr:Hash_trie dbr:Hashed_array_tree dbr:Hashlife dbr:K-independent_hashing dbr:K-mer dbr:Lazy_deletion dbr:Linear_hashing dbr:Linear_probing dbr:Linked_list dbr:List_(abstract_data_type) dbr:X-fast_trie dbr:Hash_Table dbr:Static_hashing dbr:3SUM dbr:A*_search_algorithm dbr:Adjacency_list dbr:Cyclometer dbr:DBM_(computing) dbr:Drizzle_(database_server) dbr:Dynamic-sized_hash_table dbr:EXtremeDB dbr:AlphaZero dbr:Facebook dbr:Four_fours dbr:Balls_into_bins_problem dbr:PAQ dbr:PHP dbr:Cdb_(software) dbr:Dirhash dbr:Fat_comma dbr:Flow-based_programming dbr:Forwarding_plane dbr:Fowler–Noll–Vo_hash_function dbr:Gnutella2 dbr:Google_litigation dbr:Judy_array dbr:Hash dbr:Zobrist_hashing dbr:Page_replacement_algorithm dbr:Predecessor_problem dbr:Purely_functional_programming dbr:Radix_tree dbr:Read-copy-update dbr:Relational_database dbr:Rete_algorithm dbr:2-choice_hashing dbr:Harbour_(programming_language) dbr:Hash_tables dbr:History_of_Ruby dbr:Baby-step_giant-step dbr:Cost_distance_analysis dbr:The_Dark_Mod dbr:Jeffrey_Vitter dbr:Prime_number dbr:Soft-body_dynamics dbr:Arthur_Samuel_(computer_scientist) dbr:At_sign dbr:Abstraction_(computer_science) dbr:Accumulator_(cryptography) dbr:Acoustic_fingerprint dbr:ChessV dbr:Key_clustering dbr:Bin_(computational_geometry) dbr:Bit_array dbr:Block_nested_loop dbr:Bloom_filters_in_bioinformatics dbr:Blue_(queue_management_algorithm) dbr:Coalesced_hashing dbr:Collection_(abstract_data_type) dbr:Java_collections_framework dbr:Transposition_table dbr:Model_204 dbr:Set_intersection_oracle dbr:Distributed_hash_table dbr:Dojo_Toolkit dbr:Dollar_sign dbr:Association_list dbr:Associative_array dbr:Autoencoder dbr:Autovivification dbr:BLAT_(bioinformatics) dbr:Boolean_model_of_information_retrieval dbr:Pick_operating_system dbr:PostgreSQL dbr:File_system_fragmentation dbr:Scatter_storage dbr:IPTraf dbr:Integer_sorting dbr:Metakit dbr:ObjectDatabase++ dbr:Objectivity/DB dbr:Object–relational_impedance_mismatch dbr:OpenZFS dbr:Oracle_ZFS dbr:Capacitated_minimum_spanning_tree dbr:Raima_Database_Manager dbr:Rasmus_Pagh dbr:Redis dbr:Search_algorithm dbr:Seed7 dbr:Separate_chaining dbr:Search_engine_indexing dbr:Lookup_table dbr:Mask_(computing) dbr:Memory_management_unit dbr:Scale-invariant_feature_transform dbr:Selection_algorithm dbr:Set_(abstract_data_type) dbr:Sigil_(computer_programming) dbr:Software dbr:Software_versioning dbr:Unit_disk_graph dbr:Virtual_method_table dbr:Unordered_associative_containers_(C++) dbr:Z-order_curve dbr:Exponential_search dbr:Extendible_hashing dbr:Factorial dbr:IDL_(programming_language) dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Load_factor_(computer_science) dbr:Primary_clustering dbr:The_Art_of_Computer_Programming dbr:Tracing_garbage_collection dbr:Planted_motif_search dbr:EveryDNS dbr:Fixed-radius_near_neighbors dbr:Flashcache dbr:Rendezvous_hashing dbr:Universal_hashing dbr:Quadratic_probing dbr:Multimap dbr:Multiton_pattern dbr:Symbol_table dbr:Polynomial_evaluation dbr:Self-balancing_binary_search_tree dbr:Standard_Libraries_(CLI) dbr:Non-blocking_algorithm dbr:Page_table dbr:Quotient_filter dbr:Tabulation_hashing dbr:Perl_language_structure dbr:Outline_of_Perl dbr:Outline_of_computer_science dbr:Outline_of_software_engineering dbr:XHarbour dbr:SipHash dbr:Shardmap dbr:Skip_graph dbr:Venti dbr:Unordered_map dbr:Chaining_hash_table dbr:Hash-Based_Indexes dbr:Hash-table dbr:Hash_map dbr:Hash_table_collision dbr:Hash_table_collisions dbr:Hashmap dbr:Hashtable dbr:Array_hash_table dbr:Open_hashing dbr:Direct_chaining dbr:Rehash dbr:Address-calculation_sort dbr:Collision_resolution_scheme dbr:External_chaining |
| is foaf:primaryTopic of | wikipedia-en:Hash_table |
