İçeriğe atla

Hash tablosu

Komut çizelgesiyla yapılmış küçük bir telefon defteri.

Bilişim bilimlerinde komut çizelgesi (İng. hash table veya hash map - hash = doğramak), komut işlevini tanıyıcı değer olarak bilinen benzersiz anahtarı bir değerle (mesela kişi adını telefon numarasıyla) eşleyen bir veri yapısıdır. Böylece komut çizelgesi bir birleşik dizidir. Komut işlevi, ilişkin değerin arandığı anahtarı bir dizi elemanının indisine ("dilim" veya "kova") çevirir (doğramaya benzediğinden "hash" denmiştir).

İdealde komut işlevinin mümkün olan her anahtarı farklı benzersiz dilim indisine eşlemesi, gerçekte (komut anahtarları sâbit, yani tabloya oluşumundan sonra yeni öge eklenmemesi durumu dışında) enderdir. Çoğu komut çizelgesi tasarımları "çarpışmaları", yani farklı anahtarlara aynı komut değerinin bulunması durumunu normal olarak görerek bir şekilde uzlaştırır. Uygun boyutlandırılmış bir komut çizelgesinda her bakış için ortalama maliyet (gerekli komut sayısı), çizelgede depolanmış eleman sayısından bağımsızdır. Ayrıca birçok komut çizelge tasarımları, anahtar-değer çiftlerinin keyfî araya sokuluş ve çıkarışlarına (aslında sönümlenmiş[1]) sabit işlem başı maliyetle izin verir.[2][3]

Birçok durumda komut tablolarının arama ağaçları veya herhangi bir çizelge başvuru yapısından daha verimli olduğu ortaya çıkar. Bu sebeple birçok yazılım çeşidinde, özellikle birleşmeli dizinlerde, veritabanı indekslemesinde, önbelleklerde ve kümelerde kullanılır.

Komut çizelgeleri kriptografi ve veri iletiminde kullanılan komut listeleri ve komut ağaçlarıyla karıştırmamalıdır.

Komut işlevi

Komut çizelgesi algoritmasının temelinde basit bir dizin ögesidir. Bu ögeye kısaca komut çizelgesi (İng. hash table). Komut çizelgesi algoritmaları, veri ögelerinin kiplemelerinden bir indeks hesaplayıp bunu veriyi bir dizine yerleştirmeye kullanılır. Bu hesabın uygulaması komut işlevidir ve f:

indeks = f(kipleme, dizinUzunlugu)

Komut işlevi, veri kiplemesi dizininden oluşturulan indeksi hesaplar. dizinUzunlugu, dizinin büyüklüğüdür.

Birleştirici dil veya başka alçak düzeyli dillerde çoğu zaman sıradan bir komut işleviyle bir veya iki satıriçi makine komutu içeren bir indeks oluşturulur.


Kaynakça

  1. ^ Charles E. Leiserson, Amortized Algorithms, Table Doubling, Potential Method 7 Ağustos 2009 tarihinde Wayback Machine sitesinde arşivlendi. Lecture 13, course MIT 6.046J/18.410J Introduction to Algorithms - Fall 2005
  2. ^ Donald Knuth (1998). The Art of Computer Programming'. 3: Sorting and Searching (2. bas.). Addison-Wesley. ss. 513-558. ISBN 0-201-89685-0. 
  3. ^ Cormen, Thomas H. (2001). Introduction to Algorithms. 2. MIT Press and McGraw-Hill. ss. 221-252. ISBN 978-0-262-53196-2. 

İlgili Araştırma Makaleleri

<span class="mw-page-title-main">Arama motoru</span>

Web arama motoru veya internet arama motoru, web'de sistematik bir şekilde internet kullanıcılarının istedikleri bilgilere anında erişebilmek için sıkça kullandıkları bir yazılım türüdür. Birincil işlevi internette veya internetin bir kısmında bulunmuş olan verileri bir araya getirmek ve raporlamaktır. Arama sonuçları genellikle satırlara ayrılmış sonuç sayfaları şeklinde sunulur. Bulunan bilgiler arasında web sayfası bağlantıları, görseller, videolar, infografikler, yazılar, akademik makaleler ve diğer dosya türleri yer alabilir. Arama motoru, çıktı olarak elde edilmiş kayıtlar ve bilgilerin hepsini birbiriyle karşılaştırarak sorgulayan, bir sorgunun kabul edilebilmesi için gerekli faaliyetleri gerçekleştiren, elde edilen verilerin performanslarının en yüksek olmasını amaçlayan bir sorgulama ve bulma mekanizmasıdır. Bazı arama motorları, veri tabanlarında ve kamuya açık dizinlerde bulunan bilgileri de indeksler. Bu noktada toplanan veriler, web sitesi URL’sini, web sitesinin içeriğini açıklayan bazı anahtar kelimeleri veya anahtar kelime gruplarını, web sayfasını oluşturan kod yapısını ve web sitesinde verilen bağlantıları içerir. Arama motorları, insanlar tarafından derlenen web dizinlerinin aksine, "örümcek" denilen botlar tarafından toplanan bilgileri belirli bir algoritma yardımıyla gerçek zamanlı olarak yansıtabilirler. Ve de günümüzde World Wide Web ile çok iyi bir hale gelen arama motorları, giderek profesyonelleşmeye devam etmektedir.

<span class="mw-page-title-main">AES</span> Şifreleme standartı

AES, elektronik verinin şifrelenmesi için sunulan bir standarttır. Amerikan hükûmeti tarafından kabul edilen AES, uluslararası alanda da defacto şifreleme (kripto) standardı olarak kullanılmaktadır. DES'in yerini almıştır. AES ile tanımlanan şifreleme algoritması, hem şifreleme hem de şifreli metni çözmede kullanılan anahtarların birbiriyle ilişkili olduğu, simetrik-anahtarlı bir algoritmadır. AES için şifreleme ve şifre çözme anahtarları aynıdır.

<span class="mw-page-title-main">Büyük O gösterimi</span>

Büyük O (Big-Oh) gösterimi matematiksel bir gösterim olup işlevlerin (fonksiyonların) asimptotik davranışlarını tarif etmek için kullanılır. Bir işlevin büyümesinin asimptotik üst sınırını daha basit başka bir işlev cinsinden tanımlanması demektir. İki temel uygulama alanı vardır: matematik alanında genellikle kırpılmış bir sonsuz serinin kalan terimini karakterize etmek için kullanılır; bilgisayar bilimlerinde ise algoritmaların bilgi işlemsel karmaşıklığının çözümlemesi için kullanılır.

Bilgisayar biliminde, Lexer sözcüksel analiz gerçekleştiren program parçasının adıdır. Türkçede direkt çevirisinin yapılabileceği doğru bir kelime olmayan terimlerden biri denebilir. Sözcüksel analiz kaynak kod üstünde gerçekleştirilen bir eylemdir. Sözcüksel analiz sonucunca kaynak kodun program tarafından incelenip ayrıştırılarak anahtar kelime, operatör ya da tanımlayıcılar gibi her bir ögesinin jeton olarak temsili elde edilir.

Veri yapısı, bilgisayar ortamında verilerin etkin olarak saklanması ve işlenmesi için kullanılan yapı.

<span class="mw-page-title-main">PiSi Paket Yöneticisi</span>

PiSi, 2011.2 sürümüne kadar Pardus'un güncel olarak da Pisi Linux ve Solus'un paket yöneticisidir. Bağımlılıkları takip ederek paket inşa etme, kurma, kaldırma, yükseltme ve benzeri işlevleri yerine getirir. Kullanıcı dostu bir grafiksel arayüz ve kapsamlı bir komut satırı arayüzü içerir. Geliştiriciler için tanıdık ve basit bir geliştirme ortamı sunar.

Blowfish, Bruce Schneier tarafından 1993 yılında tasarlanmış, çok sayıda şifreleyici ve şifreleme ürününe dahil olan; anahtarlanmış, simetrik bir Block Cipher dir. Blowfish ile ilgili olarak şu ana kadar etkin bir şifre çözme analizi var olmasa da, artık AES ya da Twofish gibi daha büyük ebatlı öbek şifreleyicilerine daha fazla önem verilmektedir.

<span class="mw-page-title-main">Hızlı sıralama</span>

Hızlı sıralama, günümüzde yaygın olarak kullanılan bir sıralama algoritmasıdır. Hızlı sıralama algoritması n adet sayıyı, ortalama bir durumda, karmaşıklığıyla, en kötü durumda ise karmaşıklığıyla sıralar. Algoritmanın karmaşıklığı aynı zamanda yapılan karşılaştırma sayısına eşittir.

<span class="mw-page-title-main">Dinamik dizi</span>

Dinamik dizi, tutabileceği eleman sayısının derleme zamanında bilinmesine gerek olmayan dizidir. Dinamik dizi tanımlandığında, kapasitesini belirten bir bellek tahsis edilir ve kullanımda kapasiteye erişildiğinde yeniden bir dinamik bellek tahsisi yapılır. Dinamik diziye elemanlar eklenebilir, diziden elemanlar silinebilir; dizinin boyutu azaltılabilir ve arttırılabilir. Bazı programlama dillerinde vektör adıyla anılan bu yapıyı birçok modern programlama dili kendi kütüphaneleriyle sunmaktadır.

Dizi eşleme algoritmaları olarak da adlandırılan dizi arama algoritmaları, bir ya da birkaç dizinin (örüntü) daha büyük bir dizi ya da metin içindeki yerinin bulunmasını konu edinen önemli bir dizi algoritması sınıfıdır.

Bilgisayar bilimleri'nde NoSQL, klasik ilişkisel veritabanı yönetim sistemlerinden (İVTYS) bir şekilde farklı olan veritabanı yönetim sistemleri için kullanılan bir kavramdır. Bu veri depolarının sabit tabela düzenlerine ihtiyaçları olmayabilir, alışılagelmiş join işlemleri kullanılmaz, tipik olarak yatay ölçeklemeye gidilir. Akademisyenlerce ve makalelerde tipik olarak böyle veri depolarına yapılanmış bellek denir. Bu kavram klasik ilişkisel veritabanlarını altküme olarak görür. Bu kavram aynı zamanda SQL ve Daha Fazlası olarak da adlandırılmaktadır.

<span class="mw-page-title-main">Kriptografik özet fonksiyonu</span>

Kriptografik özet fonksiyonu çeşitli güvenlik özelliklerini sağlayan bir özet fonksiyonudur. Veriyi belirli uzunlukta bir bit dizisine, (kriptografik) özet değerine, dönüştürür. Bu dönüşüm öyle olmalıdır ki verideki herhangi bir değişiklik özet değerini değiştirmelidir. Özetlenecek veri mesaj, özet değeri ise mesaj özeti veya kısaca özet olarak da adlandırılır.

<span class="mw-page-title-main">Karma işlevi</span>

Karma işlevi, değişken uzunluklu veri kümelerini, sabit uzunluklu veri kümelerine haritalayan algoritma veya alt programdır. Örneğin, bir kişinin ismi değişken uzunlukta ise, tekil tam sayı olarak karıştırılabilir. Karma işlevlerinden geri dönen değerlere, karma değerleri, karma kodları, karma toplamları, kontrol toplamları (checksums) veya basit olarak karmalar olarak isimlendirilir.

<span class="mw-page-title-main">Öznitelik çıkarımı</span>

Makine öğrenimi, örüntü tanıma ve görüntü işleme alanlarında kullanılan öznitelik çıkarımı, girdi olarak verilen ölçülmüş verileri kullanarak türetilmiş değerler (öznitelikler) oluşturur. Türetilen değerlerin bilgilendirici ve artıksız olması, öğrenme sürecini kolaylaştırıcı olması ve bazı durumlarda insan uzmanlar tarafından daha iyi anlaşılabilir (yorumlanabilir) olması amaçlanır. Öznitelik çıkarımı, boyut indirgeme konusuyla ilişkilidir.

İlişkisel veritabanı, 1970 yılında Edgar Frank Codd tarafından önerildiği gibi, organizasyonu ilişkisel veri modeline dayanan bir dijital veritabanıdır. İlişkisel veritabanlarını korumak için kullanılan çeşitli yazılım sistemleri bir ilişkisel veritabanı yönetim sistemi (RDBMS) olarak bilinir. Neredeyse tüm ilişkisel veritabanı sistemleri, sorgulama ve veritabanının bakımı için dil olarak SQL(Structured Query Language) kullanmaktadırlar.

Bir veritabanı dizini, veri ve dizinin veri yapısını koruyan ve ek depolama alanı maliyetiyle bir veritabanı tablosundaki veri alma işlemlerinin hızını artıran bir veri yapısıdır. İndeksler, bir veritabanı tablosuna yapılan bütün erişimlerde, veritabanı tablosundaki her satırı tek tek aramaya gerek kalmadan hızlı bir şekilde verileri bulmak için kullanılır. İndeksler, hızlı rastgele aramalarda ve sipariş edilen kayıtların verimli bir biçimde erişimine olanak sağlayan bir veritabanı tablosunun bir veya daha fazla sütunu kullanılarak ve genişletilerek oluşturulabilir.

<span class="mw-page-title-main">Anahtar çizelgesi</span>

Kriptografide ürün şifreleri, verilerin (de)şifrelenmesinin genelde çevrimlerin iterasyonu ile yapıldığı belirli türdeki şifrelemelerdir. Çevrim sabiti olarak adlandırılan çevrime özgü sabit değerler ve çevrim anahtarı olarak adlandırılan şifre anahtarından türetilmiş çevrime özgü veriler haricinde her bir çevrim için kurgu genellikle aynıdır. Anahtar çizelgesi, tüm çevrim anahtarlarını anahtardan hesaplayan bir algoritmadır.

Kriptografide, scrypt, Colin Percival tarafından Tarsnap çevrimiçi yedekleme hizmeti için oluşturulan bir parola tabanlı anahtar türetme fonksiyonudur. Bu algoritma, büyük miktarda bellek gerektirerek büyük ölçekli özel donanım saldırılarını gerçekleştirmeyi pahalı hale getirmek için özel olarak tasarlanmıştır. 2016 yılında, scrypt algoritması IETF tarafından RFC 7914 olarak yayınlandı. Scrypt algoritmasının, ArtForz kullanıcı adına sahip ve gerçek adı bilinmeyen bir programcı tarafından implemente edilmiş, basitleştirilmiş bir sürümü, önce Tenebrix'te ve ardından Fairbrix ve Litecoin olmak üzere bir dizi kripto para birimi tarafından iş kanıtı şeması olarak kullanıldı.

Kriptografide, ilklendirme vektörü kısaca İV ya da ilklendirme değişkeni, tipik olarak rastgele veya sözde rassal olması gereken bir şifreleme temelinin sabit boyuta sahip olan girdisidir. Bu rastgelelik, şifreleme işlemlerinde anlamsal güvenliği sağlamak için çok önemlidir. Anlamsal güvenlik tek bir şifreleme yönteminin aynı anahtar ile tekrar tekrar kullanılmasının şifrelenmiş mesajın bölümleri arasındaki ilişkileri çıkarmasına izin vermediği bir özelliktir. Blok şifreleri için, İV kullanımı çalışma kipleri ile açıklanmaktadır. Ayrıca, evrensel hash fonksiyonları ve buna dayanan mesaj kimlik doğrulama kodları gibi diğer temel öğeler için de rastgeleleştirme gereklidir.

Kriptografide, bir kriptografik hash üzerindeki bir çarpışma saldırısı, aynı hash değerini üreten iki girdi bulmaya çalışır, yani bir hash çarpışması. Bu, belirli bir hedef karma değerinin belirtildiği bir ön görüntü saldırısı nın aksine bir saldırıdır. Kabaca iki tür çarpışma saldırısı vardır: