Hashes: Tablolar, Listeler ve Haritalar, Oh My?

Question

Çeşitli karma veri yapıları, özellikle hash tabloları, karma listeleri ve karma haritaları için bazı beton (laymen; süper-akademik olmayan) tanımları bulmaya çalışıyorum. Çevrimiçi aramalar, tüm bunlara birçok yararlı bağlantı sağlar, ancak diğerlerinin her birinin kullanılması uygun olduğunda açık tanımlamalar vermez.

(1) Pratik açıdan bakıldığında, bu 3 arasındaki fark nedir?

(2) Çalışma süreleri nasıl değişir? Birinin diğer karma türleri üzerinde kullanılması veya önlenmesi gerektiğinde açık örnekler var mı?

(3) Bunların her biri Harita ADT’si ile nasıl ilgilidir? Bunların hepsi sadece farklı uygulamaların mı yoksa farklı hayvanların mı?

Burada herhangi bir fikir için teşekkürler!

Answer 1

Anahtarlar ve değerler arasında eşlemeyi içeren soyut bir veri yapısı var. Map, Dictionary, Table, Association Table ve daha fazlası dahil olmak üzere birkaç farklı adı vardır.

Bu veri yapısı tarafından desteklenmesi gereken en temel işlemler, ilişkili anahtarını vererek bir değerin eklenmesi, kaldırılması ve geri alınmasıdır. Bu temel kavram etrafında varyasyonlar ve eklemeler vardır - örneğin, bazı yapılar tüm anahtar-değer çiftleri üzerinde yinelemeyi desteklemektedir, bazı yapılar anahtar başına birden çok değeri desteklemektedir. Ayrıca, çeşitli uygulamalar arasındaki zaman ve mekan karmaşıklığı arasında da bir fark vardır.

Bu veri yapısı için kullanılabilen birden çok uygulama arasında, en popüler olanlardan bazıları hızlı erişim süreleri için hash functions kullanır. Bu uygulamalar bazen Hash Table veya Hash Map adıyla çağrılabilir, read more about them in Wikipedia yapabilirsiniz. Performans aynı zamanda hash tablosu uygulamaları arasında da değişmekte olup, bir miktar amortize edilmiş O (1) ekleme ve erişim karmaşıklığı (kullanılan çok fazla alanın fiyatı) ile birlikte değişmektedir. Diğer bir deyişle, farklı bir şeydir ve bir veri yapısının gerçek yapılarından daha fazlası ile ilgilidir. Bir karma listesi genellikle yalnızca karma değerlerin düzenli bir listesidir, bu konuda özel bir şey yoktur. Büyük bir veri parçasının bütünlüğünü doğrularken kullanılır - bu durumda çeşitli veri parçalarının bağımsız olarak doğrulanmasına izin verir, sadece kötü parçaların sabitlenmesine veya geri alınmasına izin verir. Bu, tüm veri parçasını hasara uğratmak için tek bir hash değerinin kullanılmasından farklıdır; bu durumda bir arıza, tüm verilerin tekrar düzeltilmesi veya yeniden alınması anlamına gelir.