avatarJen-Hsuan Hsieh (Sean)

Free AI web copilot to create summaries, insights and extended knowledge, download it at here

6627

Abstract

s="gist-iframe" src="/gist/JenHsuan/075a959ee274f0051fd0cbe496244eba.js" allowfullscreen="" frameborder="0" height="undefined" width="undefined"> </div> </div> </figure></iframe></div></div></figure><h1 id="4a3d">3. Separate chaining table</h1><h2 id="0e6e">Collision</h2><ul><li>Two distinct keys hashing to same index</li></ul><h2 id="aee8">Collision resolution</h2><ul><li>Algorithm and data structure to handle two keys that hash to the same array index</li></ul><h2 id="b92b">Separate chaining table</h2><ul><li>To solve the collision issues efficiently</li><li>Use an array of <code>M < N</code> linked lists</li></ul><figure id="7151"><img src="https://cdn-images-1.readmedium.com/v2/resize:fit:800/0*CTkSY_QcNN4yIsYh.png"><figcaption>source: <a href="https://readmedium.com/learning-data-structure-in-javascript-for-beginners-f5752363a4e1#8804">https://readmedium.com/learning-data-structure-in-javascript-for-beginners-f5752363a4e1#8804</a></figcaption></figure><h2 id="747f">Implementation</h2><ul><li>Number of probes for search/insert is proportional to <code>N/M</code> (<code>M</code> time faster than sequenced search)</li><li><code>M</code> too large => too many empty chains</li><li><code>M</code> too small => chains too long</li><li>Typical choice: <code>M ~ N/5</code> -> constant-time operations</li></ul> <figure id="96f9"> <div> <div>

            <iframe class="gist-iframe" src="/gist/JenHsuan/c0aaca5b2c07b0865aaf09351030f05f.js" allowfullscreen="" frameborder="0" height="undefined" width="undefined">
          </div>
        </div>
    </figure></iframe></div></div></figure><h1 id="905d">4. Linear probing</h1><ul><li>Map key to integer i between 0 and M — 1</li><li>Array size M must be greater than number of key-value pairs N</li><li>Search table index <code>i</code>; if occupied but no match, try <code>i + 1</code>, <code>i + 2</code>, etc</li></ul><h2 id="36a8">Implementation</h2>
    <figure id="eb3a">
        <div>
          <div>
            
            <iframe class="gist-iframe" src="/gist/JenHsuan/90564ce134b0fb16089674cb8f35e388.js" allowfullscreen="" frameborder="0" height="undefined" width="undefined">
          </div>
        </div>
    </figure></iframe></div></div></figure><h1 id="acc2">5. Separate chaining table vs. Linear probing</h1><h2 id="5817">Separate chaining table</h2><ul><li>Easier to implement delete</li><li>Performance degrades gracefully</li><li>Clustering lass sensitive to poorly-designed hash function</li></ul><h2 id="c0fc">Linear probing</h2><ul><li>Less wasted space</li><li>Better cache performance</li></ul><h1 id="3607">6. Hash tables vs. balanced search trees</h1><h2 id="d4ad">Hash tables</h2><ul><li>Simpler to code</li><li>No effective alternative for unordered keys</li><li>Faster for simple keys (a few arithmetic operations verses log N compares)</li><li>Better system support in Java for strings (e.g., cached hash code)</li></ul><h2 id="f06b">Balanced search trees</h2><ul><li>Stronger performance guarantee</li><li>Support for ordered ST operations</li><li>Easier to implement <code>compareTo()</code> correctly than <code>equals()</code> and <code>hashCode()</code></li></ul><h2 id="d955">Java system includes both</h2><ul><li>Red-black BSTs: <code>java.util.TreeMap</code>, <code>java.util.TreeSet</code></li><li>Hash tables: <code>java.util.HashMap</code>,<code>java.util.IdentityHashMap</code></li></ul><h1 id="644f">7. Completed code in JavaScript</h1><ul><li>completed by myself, not from the official video</li></ul><div id="ae7f" class="link-block">
      <a href="https://readmedium.com/learning-data-structure-in-javascript-for-beginners-f5752363a4e1">
        <div>
          <div>
            <h2>Learning data structure in JavaScript for beginners</h2>
            <div><h3>It’s the note for learning data structure in JavaScript. I studied the source code form trekhleb’s Github repository…</h3></div>
            <div><p>medium.com</p></div>
          </div>
          <div>
            <div style="background-image: url(https://miro.readmedium.com/v2/resize:fit:320/1*MSRVgtaB1NSWFnrP13x-jQ.png)"></div>
          </div>
        </div>
      </a>
    </div><h1 id="ff6a">Week 5 Programming Assignment: KD-Tree</h1><p id="b336">Give a bunch of points and draw a rectangle by the mouse, calculate the points inside the rectangle.</p><p id="8463">Implement in two ways.</p><ol><li>brute-force implementation (PointSET.java)</li><li>KD-tree implementation (KdTree.java)</li></ol><h2 id="40ba">Requirements in detail</h2><div id="7a68" class="link-block">
      <a href="https://coursera.cs.princeton.edu/algs4/assignments/kdtree/specification.php">
        <div>
          <div>
            <h2>Programming Assignment 5: Kd-Trees</h2>
            <div><h3>x- and y-coordinates between 0 and 1) using a2d-tree to support efficientrange search (find all of the points contained…</h3></div>
            <div><p>coursera.cs.princeton.edu</p></div>
          </div>
          <div>
            <div style="background-image: url(https://miro.readmedium.com/v2/resize:fit:320/0*0wq5sV-JkACcJeeQ)"></div>
          </div>
        </div>
      </a>
    </div><h2 id="c5f5">Solutions</h2><ul><li>PointSET.java</li></ul>
    <figure id="d8e1">
        <div>
          <div>
            
            <iframe class="gist-iframe" src="/gist/JenHsuan/56c71530e76ff42c1cb468fac8672358.js" allowfullscreen="" frameborder="0" height="undefined" width="undefined">
          </div>
        </div>
    </figure></iframe></div></div></figure><ul><li>KdTree.java</li></ul>
    <figure id="b0f9">
        <div>
          <div>
            
            <iframe class="gist-iframe" src="/gist/JenHsuan/b9ec58d563a3b392cc9efd79ed1cf912.js" allowfullscreen="" frameborder="0" height="undefined" width="undefined">
          </div>
        </div>
    </figure></iframe></div></div></figure><h2 id="4e73">Grades</h2><figure id="a63d"><img src="https://cdn-images-1.readmedium.com/v2/resize:fit:800/1*8xZ-02kUeZs-gVWpfvd0uw.png"><figcaption></figcaption></figure><h1 id="2ad6">Summary</h1><p id="67b1"><i>Thanks for your patient. I am <a href="https://www.linkedin.com/in/jen-hsuan-hsieh-6a13347a/">Sean</a>. I work as a software engineer.</i></p><p id="95c5"><i>This article is my note. Please feel free to give me advice if any mistakes. I

Options

am looking forward to your feedback.</i></p><ul><li>Subscribe me</li></ul><div id="00b7" class="link-block"> <a href="https://medium.com/@seanhsieh_63050/membership"> <div> <div> <h2>Join Medium with my referral link — Jen-Hsuan Hsieh (Sean)</h2> <div><h3>As a Medium member, a portion of your membership fee goes to writers you read, and you get full access to every story…</h3></div> <div><p>medium.com</p></div> </div> <div> <div style="background-image: url(https://miro.readmedium.com/v2/resize:fit:320/0*HotGzJ9QwFkeUJCo)"></div> </div> </div> </a> </div><ul><li>The Facebook page for articles</li></ul><div id="633c" class="link-block"> <a href="https://www.facebook.com/imalayman"> <div> <div> <h2>A Layman</h2> <div><h3>A Layman. 81 likes. The page sharing the information about programming languages, algorithm, databases, devops and…</h3></div> <div><p>www.facebook.com</p></div> </div> <div> <div style="background-image: url(https://miro.readmedium.com/v2/resize:fit:320/0*7t8weBH0eq-il9Lq)"></div> </div> </div> </a> </div><ul><li>The latest side project: Daily Learning</li></ul><div id="af2a" class="link-block"> <a href="https://daily-learning.herokuapp.com/"> <div> <div> <h2>ALayman Daily Learning</h2> <div><h3>Daily learning provides articles, challenges, or videos to people who are also self-learner for programming.</h3></div> <div><p>daily-learning.herokuapp.com</p></div> </div> <div> <div style="background-image: url(https://miro.readmedium.com/v2/resize:fit:320/0*7820hJWu4Uq6b1eH)"></div> </div> </div> </a> </div><h1 id="e3cf">Related topics</h1><p id="0421">How to use the two-way binding in Knout.js and ReactJS?</p><div id="bb06" class="link-block"> <a href="https://readmedium.com/how-to-use-the-two-way-binding-in-knout-js-and-reactjs-afea126d0236"> <div> <div> <h2>How to use the two-way binding in Knout.js and ReactJS?</h2> <div><h3>Components built by different frameworks must have the same action in one website. What we have to realize is how to…</h3></div> <div><p>medium.com</p></div> </div> <div> <div style="background-image: url(https://miro.readmedium.com/v2/resize:fit:320/1*SK9-uglh85Hl4wAh3OHQ_g.png)"></div> </div> </div> </a> </div><p id="7d15">Learn how to use SignalR to build a chatroom application</p><div id="ebac" class="link-block"> <a href="https://readmedium.com/learn-how-to-use-signalr-to-build-a-chatroom-application-63e8bb8049ff"> <div> <div> <h2>Learn how to use SignalR to build a chatroom application</h2> <div><h3>The Introduction of SignalR</h3></div> <div><p>medium.com</p></div> </div> <div> <div style="background-image: url(https://miro.readmedium.com/v2/resize:fit:320/1*j6m4jnkuRKkQ6rrkqLFeGA.png)"></div> </div> </div> </a> </div><p id="6252">My reflection of <effective sql="">:</effective></p><div id="a401" class="link-block"> <a href="https://readmedium.com/how-to-design-the-data-model-my-reflection-of-effective-sql-adba6376588a"> <div> <div> <h2>How To Design The Data Model? — My reflection of <effective sql=""></effective></h2> <div><h3><effective 61="" sql:="" specific="" ways="" to="" write="" better="" sql=""> gave me many tips for using the database.</effective></h3></div> <div><p>medium.com</p></div> </div> <div> <div style="background-image: url(https://miro.readmedium.com/v2/resize:fit:320/1*trYud-lAkP2-bXo82U9bQA.png)"></div> </div> </div> </a> </div><div id="249d" class="link-block"> <a href="https://readmedium.com/how-to-design-the-index-my-reflection-of-effective-sql-b23d24212974"> <div> <div> <h2>How To Design The Index? — My reflection of <effective sql=""></effective></h2> <div><h3><effective 61="" sql:="" specific="" ways="" to="" write="" better="" sql=""> gave me many tips for using the database.</effective></h3></div> <div><p>medium.com</p></div> </div> <div> <div style="background-image: url(https://miro.readmedium.com/v2/resize:fit:320/1*l4nVJqhrI1_sFMy2zQ8N0w.png)"></div> </div> </div> </a> </div><div id="6af9" class="link-block"> <a href="https://readmedium.com/whats-if-we-can-t-change-the-design-my-reflection-of-effective-sql-3704b87c49b5"> <div> <div> <h2>What if we can’t change the design? — My reflection of <effective sql=""> Part 3</effective></h2> <div><h3><effective 61="" sql:="" specific="" ways="" to="" write="" better="" sql=""> gave me many tips for using the database.</effective></h3></div> <div><p>medium.com</p></div> </div> <div> <div style="background-image: url(https://miro.readmedium.com/v2/resize:fit:320/1*jqUMxB_afM-552DjqBo3gA.png)"></div> </div> </div> </a> </div><p id="75de">IT & Network:</p><div id="79e8" class="link-block"> <a href="https://readmedium.com/back-to-the-basic-introduction-to-dns-f63aebe7bee7"> <div> <div> <h2>Back to the basic: Introduction to DNS</h2> <div><h3>I decided to back to the basic and enhance these bits of knowledge. I also expect that this article can help someone…</h3></div> <div><p>medium.com</p></div> </div> <div> <div style="background-image: url(https://miro.readmedium.com/v2/resize:fit:320/1*m4nxtUjDkrX9lClzHnnboA.png)"></div> </div> </div> </a> </div></article></body>

Algorithms, Part 1 Course from Princeton — Hash table and Week 5 Assignment KD-Tree

Introduction

Algorithms, Part 1 is a solid course for IT or software engineers to learn algorithms which are provided by Princeton. Of course, we still have to take time to clarify the concepts after completing the class.

Hash table is an efficient way for the unordered keys. Java provides better system supports for the hash table than the binary search tree. In this article, we will focus on how they works.

About this Series

This series aims to wrap up contents of Algorithms, Part 1.

Agenda

It includes the following topics in this article.

1. Hash table

From the previous article, we know that the red-black BST (a kind of balanced BSTs) guarantees the performance of ST operations on the Log N level.

Are there any ways to retrieve better performance?

Actually, we can achieve the better performances with the hash table. Under the uniform hashing assumption, the hash table can do the task with the constant level.

There are two phases to organize the hash table.

  1. Hashing
  2. Table (Separate chaining table/Linear probing)

2. Hashing

  • Save items in a key-indexed table (index is a function of the key)

Hash function

  • Method for computing array index from key
  • Idealistic goal: scramble the keys uniformly to produce a table index

Java library implementation for the Hash function

All Java classes inherit a method hashCode().

  • hashCode()for Integer (may return the negative number)
  • hashCode()for Boolean
  • hashCode()for Double: xor most significant 32-bits with least significant 32-bits
  • hashCode()for string: - Honer’s method - Turn the i^th character of s to the unicode

User-defined implementation for the Hash function

  • Combine each significant field using 31x + y rule
  • If the field is a primary type, use wrapper type hashCode()
  • Modular hashing: return a hash between 0 and M — 1

3. Separate chaining table

Collision

  • Two distinct keys hashing to same index

Collision resolution

  • Algorithm and data structure to handle two keys that hash to the same array index

Separate chaining table

  • To solve the collision issues efficiently
  • Use an array of M < N linked lists
source: https://readmedium.com/learning-data-structure-in-javascript-for-beginners-f5752363a4e1#8804

Implementation

  • Number of probes for search/insert is proportional to N/M (M time faster than sequenced search)
  • M too large => too many empty chains
  • M too small => chains too long
  • Typical choice: M ~ N/5 -> constant-time operations

4. Linear probing

  • Map key to integer i between 0 and M — 1
  • Array size M must be greater than number of key-value pairs N
  • Search table index i; if occupied but no match, try i + 1, i + 2, etc

Implementation

5. Separate chaining table vs. Linear probing

Separate chaining table

  • Easier to implement delete
  • Performance degrades gracefully
  • Clustering lass sensitive to poorly-designed hash function

Linear probing

  • Less wasted space
  • Better cache performance

6. Hash tables vs. balanced search trees

Hash tables

  • Simpler to code
  • No effective alternative for unordered keys
  • Faster for simple keys (a few arithmetic operations verses log N compares)
  • Better system support in Java for strings (e.g., cached hash code)

Balanced search trees

  • Stronger performance guarantee
  • Support for ordered ST operations
  • Easier to implement compareTo() correctly than equals() and hashCode()

Java system includes both

  • Red-black BSTs: java.util.TreeMap, java.util.TreeSet
  • Hash tables: java.util.HashMap,java.util.IdentityHashMap

7. Completed code in JavaScript

  • completed by myself, not from the official video

Week 5 Programming Assignment: KD-Tree

Give a bunch of points and draw a rectangle by the mouse, calculate the points inside the rectangle.

Implement in two ways.

  1. brute-force implementation (PointSET.java)
  2. KD-tree implementation (KdTree.java)

Requirements in detail

Solutions

  • PointSET.java
  • KdTree.java

Grades

Summary

Thanks for your patient. I am Sean. I work as a software engineer.

This article is my note. Please feel free to give me advice if any mistakes. I am looking forward to your feedback.

  • Subscribe me
  • The Facebook page for articles
  • The latest side project: Daily Learning

Related topics

How to use the two-way binding in Knout.js and ReactJS?

Learn how to use SignalR to build a chatroom application

My reflection of :

IT & Network:

Software Development
Hash Table
Data Structures
Java
Princeton
Recommended from ReadMedium
avatarAshish Pratap Singh
How I Mastered Data Structures and Algorithms

Getting good at Data Structures and Algorithms (DSA) helped me clear interviews at Amazon, Google and Microsoft.

6 min read
avatarHùng Trần
Stop using if-else statements in Java

The tale goes that there is an ancient legacy system, my colleague coded thousands of lines from top to bottom, and each block added…

6 min read
avatarRuchira Madhushan Rajapaksha
Is Today’s OOP Aligned with Alan Kay’s Original Concept?

Why do languages like C# and Java fall short of Alan Kay’s original Object-Oriented Vision?

5 min read
avatarGul Ershad
Resilience Patterns in Microservices

Introduction

9 min read
avatarSelcuk Ozdemir
Say Goodbye to Try/Catch with This New ECMAScript Operator! 🚀

Introducing the ?= Operator: JavaScript’s New Error Handling Hero

4 min read
avatarJagadesh Jamjala
Data Engineering and the CAP Theorem: Best Practices

The CAP theorem is a fundamental concept in distributed systems that states a distributed data store can only provide two out of three…

2 min read