Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Hashing and Sorting

In course

CS-322: Introduction to database systems

This course provides a deep understanding of the concepts behind data management systems. It covers fundamental data management topics such as system architecture, data models, query processing and optimization, database design, storage organization, and t ...

Description

This lecture covers the concepts of hashing and sorting, starting with an introduction to static hashing and the use of hash functions to distribute values. It then delves into extendible hashing, which avoids overflow pages by splitting full buckets. The lecture also explains linear hashing as a dynamic hashing scheme and discusses the main idea behind it. Examples are provided to illustrate the process of handling inserts and the impact of certain values on the hashing process. The lecture concludes with a comparison between external sorting and unclustered indexes, highlighting the importance of external merge sort in minimizing disk I/O costs.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

Instructors (3)

Anastasia Ailamaki

Christoph Koch

Angelos Christos Anadiotis

Official source

Ontological neighbourhood

Theoretical computer science

Algorithms and data structures: Analysis of algorithms

Related concepts (32)

Sorting algorithm

In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. Efficient sorting is important for optimizing the efficiency of other algorithms (such as search and merge algorithms) that require input data to be in sorted lists. Sorting is also often useful for canonicalizing data and for producing human-readable output.

Hash function

A hash function is any function that can be used to map data of arbitrary size to fixed-size values, though there are some hash functions that support variable length output. The values returned by a hash function are called hash values, hash codes, digests, or simply hashes. The values are usually used to index a fixed-size table called a hash table. Use of a hash function to index a hash table is called hashing or scatter storage addressing.

External sorting

External sorting is a class of sorting algorithms that can handle massive amounts of data. External sorting is required when the data being sorted do not fit into the main memory of a computing device (usually RAM) and instead they must reside in the slower external memory, usually a disk drive. Thus, external sorting algorithms are external memory algorithms and thus applicable in the external memory model of computation. External sorting algorithms generally fall into two types, distribution sorting, which resembles quicksort, and external merge sort, which resembles merge sort.

Merge sort

In computer science, merge sort (also commonly spelled as mergesort) is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the relative order of equal elements is the same in the input and output. Merge sort is a divide-and-conquer algorithm that was invented by John von Neumann in 1945. A detailed description and analysis of bottom-up merge sort appeared in a report by Goldstine and von Neumann as early as 1948.

Hash table

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.

Related lectures (51)

Merge Sort: Sorting Algorithm

Explains the merge sort algorithm, its correctness, and time complexity compared to other sorting algorithms.

Hashing and Quick Sort

Covers the efficient implementation of hash tables and the Quick Sort algorithm.

Sorting Algorithms: Selection and Insertion

Introduces selection and insertion sorting algorithms, explaining their correctness and time complexity.

Optimization Algorithms: Greedy Approach

Explores optimization problems and greedy algorithms for efficient decision-making.

Reservoirs and Dams: Hydraulic Construction and Sizing