Why use an Array to implement a "list" instead of a Hash Table? - GeeksforGeeks (2024)

Table of Contents

What is an Array? C++ Java Python3 C# Javascript What is a Hash Table What is a List? C++ Java Python3 C# Javascript Why use an “Array” to implement a “List” instead of a “Hash Table”? Please Login to comment... Similar Reads Thank You!

Courses
- DSA to Development
- Newly Launched!
  - Master Django Framework
  - Become AWS Certified
- For Working Professionals
  - Data Science Training Program
  - JAVA Backend Development (Live)
  - DevOps Engineering (LIVE)
- For Students
  - Placement Preparation Course
  - Data Science (Live)
  - Master Competitive Programming (Live)
- GATE Exam Courses
- All Courses
Tutorials
- Data Structures & Algorithms
  - DSA for Beginners
  - Data Structures
    - Arrays
    - Matrix
    - Strings
    - Linked List
    - Stack
    - Queue
    - Tree
      - Generic Tree
      - Binary Tree
      - Binary Search Tree
      - AVL Tree
      - B Tree
      - B+ Tree
      - Red Black Tree
      - Tree Data Structure Tutorial
    - Heap
    - Hashing
    - Graph
    - Set Data Structure
    - Map Data Structure
    - Advanced Data Structure

DSA Course
DSA
Interview Questions on Array
Practice Array
MCQs on Array
Tutorial on Array
Types of Arrays
Array Operations
Subarrays, Subsequences, Subsets
Reverse Array
Static Vs Arrays
Array Vs Linked List
Array | Range Queries

Open In App

Last Updated : 20 Feb, 2024

Summarize

Comments

Improve

Suggest changes

Like Article

Save

Report

What is an Array?

An array is a collection of similar data elements stored at contiguous memory locations. It is the simplest data structure where each data element can be accessed directly by only using its index number.

Array

C++

#include <iostream>

using namespace std;

// driver program

int main() {

// initaizling array

int arr[] = {1, 2, 3, 4, 5};

// printing array element

for (int i : arr) {

cout << i << " ";

}

return 0;

}

Java

Python3

# initializing list

arr = [1, 2, 3, 4, 5]

# printing list elements

for i in arr:

print(i, end=" ")

C#

using System;

class GFG {

public static void Main (string[] args) {

int[] arr = {1,2,3,4,5};

foreach(int i in arr){

Console.Write(i + " ");

}

// This code is contributed by akashish__

Javascript

// Initializing array

const arr = [1, 2, 3, 4, 5];

// Printing array elements

for (const i of arr) {

console.log(i + " ");

}

Output

1 2 3 4 5

What is a Hash Table

A Hash table is a data structure that stores some information, and the information has basically two main components, i.e., key and value. The hash table can be implemented with the help of an associative array.

What is a List?

A list is an ordered and changeable collection of data objects. Unlike an array, which can contain objects of a single type, a list can contain a mixture of objects.

C++

#include <iostream>

#include <vector>

int main() {

std::vector<int> ll = {1, 2, 3, 4, 5};

for (int num : ll) {

std::cout << num << " ";

}

return 0;

}

Java

/*package whatever //do not write package name here */

import java.util.*;

class GFG {

public static void main (String[] args) {

List<Integer> ll = Arrays.asList(new Integer[]{1,2,3,4,5});

System.out.println(ll);

}

Python3

# Python code with comments

# Define a list named 'll' containing integers 1 through 5

ll = [1, 2, 3, 4, 5]

# Iterate over each element 'num' in the list 'll'

for num in ll:

# Print the current element followed by a space

print(num, end=" ")

#this code is contributed by Utkarsh

C#

using System;

using System.Collections.Generic;

class GFG {

static void Main(string[] args) {

// Creating a list of integers using List<T> and initializing it with the provided array of integers

List<int> ll = new List<int>(new int[] { 1, 2, 3, 4, 5 });

// Printing the elements of the list

// Joining the elements into a single string separated by commas using string.Join

Console.WriteLine(string.Join(", ", ll));

}

Javascript

// Main function

function main() {

// Define an array

let ll = [1, 2, 3, 4, 5];

// Iterate through the array and print each element

for (let num of ll) {

console.log(num + " ");

}

// Invoke main function

main();

Output

1 2 3 4 5

Why use an “Array” to implement a “List” instead of a “Hash Table”?

All of the different collection data types have their specific advantages and disadvantages.

Time taken for insertion, lookup, and removal are O(1) for both arrays and hash tables in all cases. But array has a much lower constant overhead than hashtables. And arrays need less space per entry.

If you would like to remove and insert entries in a way that the following entries change their index accordingly, it would be O(n) in case of an array with n being the number of entries that need to be moved. It would also be O(n) for hashtables to do this but with a much higher constant overhead.

A list is typically ordered whereas a hashtable is not. So when you add elements into a list and expect the ordering to remain consistent then an array retains the ordering while a hashtable gives no guarantee as to the order you get back out. That’s why we use an array to implement a list instead of a hash table.

isha01795

Improve

Why and when to use Stack or Queue instead of Arrays/Lists?

Please Login to comment...

Similar Reads

Can we use Simple Queue instead of Priority queue to implement Dijkstra's Algorithm? What is Dijkstra's Algorithm? Dijkstra's Algorithm is used for finding the shortest path between any two vertices of a graph. It uses a priority queue for finding the shortest path. For more detail, about Dijkstra's Algorithm, you can refer to this article. Why Dijkstra's Algorithm uses a Priority Queue? We use min heap in Dijkstra's Algorithm beca 2 min read Why and when to use Stack or Queue instead of Arrays/Lists? Stack: A stack is a linear data structure in which elements are accessed, inserted and deleted from one end called the top of the stack. Stack follows the LIFO ( Last In First Out) approach. Two basic operations on a stack are push and pop. Queue: A queue is also a linear data structure in which elements are inserted from one end called the rear en 2 min read What are Hash Functions and How to choose a good Hash Function? Prerequisite: Hashing | Set 1 (Introduction) What is a Hash Function? A function that converts a given big phone number to a small practical integer value. The mapped integer value is used as an index in the hash table. In simple terms, a hash function maps a big number or string to a small integer that can be used as the index in the hash table. W 5 min read Hash Functions and Types of Hash functions Hash functions are a fundamental concept in computer science and play a crucial role in various applications such as data storage, retrieval, and cryptography. In data structures and algorithms (DSA), hash functions are primarily used in hash tables, which are essential for efficient data management. This article delves into the intricacies of hash 4 min read Comparison of an Array and Hash table in terms of Storage structure and Access time complexity Arrays and Hash Tables are two of the most widely used data structures in computer science, both serving as efficient solutions for storing and accessing data in Java. They have different storage structures and time complexities, making them suitable for different use cases. In this article, we will explore the differences between arrays and hash t 3 min read Why the original value cannot be recovered from a given hash value? A hash function is a mathematical function that takes input data (also known as the message or pre-image) and produces a fixed-length output called a hash value or digest. One of the main properties of a hash function is that it is designed to be a one-way function, meaning that it is computationally infeasible to recover the original input data fr 10 min read Various load balancing techniques used in Hash table to ensure efficient access time Load balancing refers to the process of distributing workloads evenly across multiple servers, nodes, or other resources to ensure optimal resource utilization, maximize output, minimize response time, and avoid overload of any single resource. Load balancing helps to improve the reliability and scalability of applications and systems, as well as r 3 min read Implementation of Hash Table in Python using Separate Chaining A hash table is a data structure that allows for quick insertion, deletion, and retrieval of data. It works by using a hash function to map a key to an index in an array. In this article, we will implement a hash table in Python using separate chaining to handle collisions. Separate chaining is a technique used to handle collisions in a hash table. 7 min read Implementation of Hash Table in C/C++ using Separate Chaining Introduction: Hashing is a technique that maps a large set of data to a small set of data. It uses a hash function for doing this mapping. It is an irreversible process and we cannot find the original value of the key from its hashed value because we are trying to map a large set of data into a small set of data, which may cause collisions. It is n 10 min read Hash Table vs Trie What is Hash Table? An array that stores pointers to records corresponding to a given element. An entry in the hash table is NIL if no existing element has a hash function value equal to the index for the entry. In simple terms, we can say that a hash table is a generalization of the array. Hash table gives the functionality in which a collection o 5 min read Hash Table vs STL Map This article focus on : Compare and contrast Hash table and an STL Map. How is the hash table implemented? If the number of inputs is small, which data structure options can be used instead of a hash table? Hash table In a hash table, a value is stored by calling a hash function on a key. Values are not stored in sorted order.Additionally, since ha 4 min read Implementing our Own Hash Table with Separate Chaining in Java All data structure has their own special characteristics, for example, a BST is used when quick searching of an element (in log(n)) is required. A heap or a priority queue is used when the minimum or maximum element needs to be fetched in constant time. Similarly, a hash table is used to fetch, add and remove an element in constant time. Anyone mus 10 min read Implementing own Hash Table with Open Addressing Linear Probing Prerequisite - Hashing Introduction, Implementing our Own Hash Table with Separate Chaining in JavaIn Open Addressing, all elements are stored in the hash table itself. So at any point, size of table must be greater than or equal to total number of keys (Note that we can increase table size by copying old data if needed). Insert(k) - Keep probing u 13 min read Hash Table Data Structure What is Hash Table?A Hash table is defined as a data structure used to insert, look up, and remove key-value pairs quickly. It operates on the hashing concept, where each key is translated by a hash function into a distinct index in an array. The index functions as a storage location for the matching value. In simple words, it maps the keys with th 7 min read Advantages of BST over Hash Table Hash Table supports following operations in O(1) time. 1) Search 2) Insert 3) Delete The time complexity of above operations in a self-balancing Binary Search Tree (BST) (like Red-Black Tree, AVL Tree, Splay Tree, etc) is O(Logn). So Hash Table seems to beating BST in all common operations. When should we prefer BST over Hash Tables, what are advan 2 min read C++ Program to implement Symbol Table Prerequisite: Symbol Table A Symbol table is a data structure used by the compiler, where each identifier in program's source code is stored along with information associated with it relating to its declaration. It stores identifier as well as it's associated attributes like scope, type, line-number of occurrence, etc. Symbol table can be implement 4 min read Program to implement ASCII lookup table ASCII stands for American Standard Code for Information Interchange. Computers can only understand numbers, so an ASCII code is the numerical representation of a character such as ‘a’ or ‘@’ or an action of some sort. ASCII lookup table is a tabular representation of corresponding values associated to a character i.e. we can lookup the correspondin 7 min read Why use a Doubly Linked List? A doubly linked list is a type of data structure that allows for efficient insertion and deletion of elements at both ends. It is beneficial in scenarios where you need to traverse in both directions, and it provides greater flexibility compared to a singly linked list. What is Doubly Linked List ?A doubly linked list is a type of linked list where 3 min read Classify strings from an array using Custom Hash Function Given an array of strings arr[] consisting of N strings, the task is to categorize the strings according to the hash value obtained by adding ASCII values % 26 of the characters in the string. Examples: Input: arr[][] = {"geeks", "for", "geeks"}Output:geeks geeksforExplanation:The hash value of string "for" is (102 + 111 + 114) % 26 = 14The hash va 8 min read Multiplication table till N rows where every Kth row is table of K upto Kth term Given a number N, the task is to print N rows where every Kth row consists of the multiplication table of K up to Kth term. Examples: Input: N = 3 Output: 1 2 4 3 6 9 Explanation: In the above series, in every Kth row, multiplication table of K upto K terms is printed. Input: N = 5 Output: 1 2 4 3 6 9 4 8 12 16 5 10 15 20 25 Approach: The idea is t 5 min read Data Structures | Hash | Question 1 A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below. Which one of the following choices gives a possible order in which the key values could have been inserted in the table? (A) 46, 42, 34, 52, 23, 33 (B) 34, 42, 23, 52, 3 2 min read Data Structures | Hash | Question 2 How many different insertion sequences of the key values using the hash function h(k) = k mod 10 and linear probing will result in the hash table shown below? (A) 10 (B) 20 (C) 30 (D) 40 Answer: (C) Explanation: In a valid insertion sequence, the elements 42, 23 and 34 must appear before 52 and 33, and 46 must appear before 33. Total number of diff 1 min read Data Structures | Hash | Question 3 The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash table? (A) A (B) B (C) C (D) D Answer: (C) Explanation: To get the idea of open addressing concept, you can go through below lines from Wikipedia 2 min read Data Structures | Hash | Question 5 Which of the following hash functions is most likely to cause clustering in a hash table? (A) h(k) = k % m (B) h(k) = floor(m * (kA mod 1)) (C) h(k) = k (D) h(k) = ((k / m) + k * m) + k % m Answer: (A) Explanation: The modulo operation in option a) results in clustering since the hash values of keys that are close to each other will also be close, 1 min read Sorting using trivial hash function We have read about various sorting algorithms such as heap sort, bubble sort, merge sort and others. Here we will see how can we sort N elements using a hash array. But this algorithm has a limitation. We can sort only those N elements, where the value of elements is not large (typically not above 10^6). Examples: Input : 9 4 3 5 8 Output : 3 4 5 8 15+ min read Full domain Hashing with variable Hash size in Python A cryptographic hash function is a special class of hash function that has certain properties which make it suitable for use in cryptography. It is a mathematical algorithm that maps data of arbitrary size to a bit string of a fixed size (a hash function) which is designed to also be a one-way function, that is, a function which is infeasible to in 5 min read Applications, Advantages and Disadvantages of Hash Data Structure Introduction : Imagine a giant library where every book is stored in a specific shelf, but instead of searching through endless rows of shelves, you have a magical map that tells you exactly which shelf your book is on. That's exactly what a Hash data structure does for your data! Hash data structures are a fundamental building block of computer sc 7 min read Hash Sort Algorithm There have always been arguments about how can be a sorting algorithm of linear time complexity be achieved, as all the traditional sorting algorithms are at least of the order of O(N*log(N)) in worst and cases. The reason for the difficulty in achieving linearly proportional time complexity in a sorting algorithm is that most of these traditional 15+ min read What is the difference between Hashing and Hash Tables? What is Hashing? Hashing refers to the process of generating a fixed-size output from an input of variable size using the mathematical formulas known as hash functions. This technique determines an index or location for the storage of an item in a data structure. It might not be strictly related to key-value pairs only if you are manipulating the d 2 min read Introduction to Rolling Hash - Data Structures and Algorithms A rolling hash is a hash function that is used to efficiently compute a hash value for a sliding window of data. It is commonly used in computer science and computational biology, where it can be used to detect approximate string matches, find repeated substrings, and perform other operations on sequences of data. The idea behind a rolling hash is 15+ min read

Article Tags :

Arrays
DSA
cpp-list
TCS-coding-questions

Practice Tags :

Arrays

Trending in News

How to Merge Cells in Google Sheets: Step by Step Guide
How to Lock Cells in Google Sheets : Step by Step Guide
#geekstreak2024 – 21 Days POTD Challenge Powered By Deutsche Bank

We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy

'); $('.spinner-loading-overlay').show(); jQuery.ajax({ url: writeApiUrl + 'create-improvement-post/?v=1', type: "POST", contentType: 'application/json; charset=utf-8', dataType: 'json', xhrFields: { withCredentials: true }, data: JSON.stringify({ gfg_id: post_id, }), success:function(result) { $('.spinner-loading-overlay:eq(0)').remove(); $('.improve-modal--overlay').hide(); $('.unlocked-status--improve-modal-content').css("display","none"); $('.create-improvement-redirection-to-write').attr('href',writeUrl + 'improve-post/' + `${result.id}` + '/', '_blank'); $('.create-improvement-redirection-to-write')[0].click(); }, error:function(e) { $('.spinner-loading-overlay:eq(0)').remove(); var result = e.responseJSON; if(result.detail.non_field_errors.length){ $('.improve-modal--improve-content .improve-modal--improve-content-modified').text(`${result.detail.non_field_errors}.`); jQuery('.improve-modal--overlay').show(); jQuery('.improve-modal--improvement').show(); $('.locked-status--impove-modal').css("display","block"); $('.unlocked-status--improve-modal-content').css("display","none"); $('.improve-modal--improvement').attr("status","locked"); $('.improvement-reason-modal').hide(); } }, }); return; } var improvement_reason_html = ""; for(var comment of commentArray) { // loop creating improvement reason list markup var comment_id = comment['id']; var comment_text = comment['suggestion']; improvement_reason_html += `

${comment_text}

`; } $('.improvement-reasons_wrapper').html(improvement_reason_html); $('.improvement-bottom-btn').html("Create Improvement"); $('.improve-modal--improvement').hide(); $('.improvement-reason-modal').show(); }, error: function(e){ $('.spinner-loading-overlay:eq(0)').remove(); // stop loader when ajax failed; }, }); }, error:function(e) { $('.spinner-loading-overlay:eq(0)').remove(); var result = e.responseJSON; if(result.detail.non_field_errors.length){ $('.improve-modal--improve-content .improve-modal--improve-content-modified').text(`${result.detail.non_field_errors}.`); jQuery('.improve-modal--overlay').show(); jQuery('.improve-modal--improvement').show(); $('.locked-status--impove-modal').css("display","block"); $('.unlocked-status--improve-modal-content').css("display","none"); $('.improve-modal--improvement').attr("status","locked"); $('.improvement-reason-modal').hide(); } }, }); } else { if(loginData && !loginData.isLoggedIn) { $('.improve-modal--overlay').hide(); if ($('.header-main__wrapper').find('.header-main__signup.login-modal-btn').length) { $('.header-main__wrapper').find('.header-main__signup.login-modal-btn').click(); } return; } } }); $('.left-arrow-icon_wrapper').on('click',function(){ if($('.improve-modal--suggestion').is(":visible")) $('.improve-modal--suggestion').hide(); else{ $('.improvement-reason-modal').hide(); } $('.improve-modal--improvement').show(); }); function loadScript(src, callback) { var script = document.createElement('script'); script.src = src; script.onload = callback; document.head.appendChild(script); } function suggestionCall() { var suggest_val = $.trim($("#suggestion-section-textarea").val()); var array_String= suggest_val.split(" ") var gCaptchaToken = $("#g-recaptcha-response-suggestion-form").val(); var error_msg = false; if(suggest_val != "" && array_String.length >=4){ if(suggest_val.length <= 2000){ var payload = { "gfg_post_id" : `${post_id}`, "suggestion" : `

${suggest_val}

`, } if(!loginData || !loginData.isLoggedIn) // User is not logged in payload["g-recaptcha-token"] = gCaptchaToken jQuery.ajax({ type:'post', url: "https://apiwrite.geeksforgeeks.org/suggestions/auth/create/", xhrFields: { withCredentials: true }, crossDomain: true, contentType:'application/json', data: JSON.stringify(payload), success:function(data) { jQuery('.spinner-loading-overlay:eq(0)').remove(); jQuery('#suggestion-section-textarea').val(""); jQuery('.suggest-bottom-btn').css("display","none"); // Update the modal content const modalSection = document.querySelector('.suggestion-modal-section'); modalSection.innerHTML = `

Thank You!

Your suggestions are valuable to us.

You can now also contribute to the GeeksforGeeks community by creating improvement and help your fellow geeks.

`; }, error:function(data) { jQuery('.spinner-loading-overlay:eq(0)').remove(); jQuery('#suggestion-modal-alert').html("Something went wrong."); jQuery('#suggestion-modal-alert').show(); error_msg = true; } }); } else{ jQuery('.spinner-loading-overlay:eq(0)').remove(); jQuery('#suggestion-modal-alert').html("Minimum 5 Words and Maximum Character limit is 2000."); jQuery('#suggestion-modal-alert').show(); jQuery('#suggestion-section-textarea').focus(); error_msg = true; } } else{ jQuery('.spinner-loading-overlay:eq(0)').remove(); jQuery('#suggestion-modal-alert').html("Enter atleast four words !"); jQuery('#suggestion-modal-alert').show(); jQuery('#suggestion-section-textarea').focus(); error_msg = true; } if(error_msg){ setTimeout(() => { jQuery('#suggestion-section-textarea').focus(); jQuery('#suggestion-modal-alert').hide(); }, 3000); } } document.querySelector('.suggest-bottom-btn').addEventListener('click', function(){ jQuery('body').append('

'); jQuery('.spinner-loading-overlay').show(); if(loginData && loginData.isLoggedIn) { suggestionCall(); return; } // load the captcha script and set the token loadScript('https://www.google.com/recaptcha/api.js?render=6LdMFNUZAAAAAIuRtzg0piOT-qXCbDF-iQiUi9KY',[], function() { setGoogleRecaptcha(); }); }); $('.improvement-bottom-btn.create-improvement-btn').click(function() { //create improvement button is clicked $('body').append('

'); $('.spinner-loading-overlay').show(); // send this option via create-improvement-post api jQuery.ajax({ url: writeApiUrl + 'create-improvement-post/?v=1', type: "POST", contentType: 'application/json; charset=utf-8', dataType: 'json', xhrFields: { withCredentials: true }, data: JSON.stringify({ gfg_id: post_id }), success:function(result) { $('.spinner-loading-overlay:eq(0)').remove(); $('.improve-modal--overlay').hide(); $('.improvement-reason-modal').hide(); $('.create-improvement-redirection-to-write').attr('href',writeUrl + 'improve-post/' + `${result.id}` + '/', '_blank'); $('.create-improvement-redirection-to-write')[0].click(); }, error:function(e) { $('.spinner-loading-overlay:eq(0)').remove(); var result = e.responseJSON; if(result.detail.non_field_errors.length){ $('.improve-modal--improve-content .improve-modal--improve-content-modified').text(`${result.detail.non_field_errors}.`); jQuery('.improve-modal--overlay').show(); jQuery('.improve-modal--improvement').show(); $('.locked-status--impove-modal').css("display","block"); $('.unlocked-status--improve-modal-content').css("display","none"); $('.improve-modal--improvement').attr("status","locked"); $('.improvement-reason-modal').hide(); } }, }); });