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

Lecture

Implementation of Sets: Hashing

In course

CS-108: Practice of object-oriented programming

Les étudiants perfectionnent leurs connaissances en Java et les mettent en pratique en réalisant un projet de taille conséquente. Ils apprennent à utiliser et à mettre en œuvre les principaux types de collections (listes, ensembles, tables associatives), e ...

Description

This lecture covers the implementation of sets using hashing, focusing on the SHashSet class. Topics include creating a hash table, adding elements, removing elements, checking for element existence, and iterating through the set. The lecture also discusses the use of iterators and consumers in the context of set operations.

Instructor

Michel Schinz

Official source

Ontological neighbourhood

Theoretical computer science

Programming language theory: High-level programming languages

Related concepts (32)

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.

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.

Perfect hash function

In computer science, a perfect hash function h for a set S is a hash function that maps distinct elements in S to a set of m integers, with no collisions. In mathematical terms, it is an injective function. Perfect hash functions may be used to implement a lookup table with constant worst-case access time. A perfect hash function can, as any hash function, be used to implement hash tables, with the advantage that no collision resolution has to be implemented.

Java syntax

The syntax of Java is the set of rules defining how a Java program is written and interpreted. The syntax is mostly derived from C and C++. Unlike in C++, in Java there are no global functions or variables, but there are data members which are also regarded as global variables. All code belongs to classes and all values are objects. The only exception is the primitive types, which are not represented by a class instance for performance reasons (though can be automatically converted to objects and vice versa via autoboxing).

Java version history

The Java language has undergone several changes since JDK 1.0 as well as numerous additions of classes and packages to the standard library. Since J2SE 1.4, the evolution of the Java language has been governed by the Java Community Process (JCP), which uses Java Specification Requests (JSRs) to propose and specify additions and changes to the Java platform. The language is specified by the Java Language Specification (JLS); changes to the JLS are managed under JSR 901.

Related lectures (35)

Implementation of Singly Linked Lists

Covers the implementation of singly linked lists in Java, focusing on concepts such as nodes, size management, adding, removing, and getting elements.

Comparing Objects: Comparable vs Comparator

Covers the concepts of Comparable and Comparator interfaces in Java, explaining how classes implement these interfaces to enable object comparison.

Implementation of Sets: Part I

Covers the implementation of inheritable classes for simplified sets in Java.

Equality, Order, and Hashing

Explains hashing, equality, and order in Java, emphasizing method compatibility for correct collection behavior.

Design Patterns: Observer