Index
Overview


This page is a listing of frequently asked questions (FAQs).

Is there a method that makes a new DynamicArray?


This is a nice question because we can let the code answer it for us.

With objects, we want to be able to code off of method headers.

Thus, for this question, we can open up the DynamicArray source file and search for the constructors -- try a search on "Public Constructors".

The constructor method headers answer our questions for us. We simply code to meet the constructor we choose to use. We do not need to read code -- the method header tells us all we need to know.

Does the constructor newEmpty() return an empty object?


In the HashTable class, we have a static factory method "newEmpty".

Yes it is correct that this method returns a new instance of a hash table.

Note that this does not mean the new hash table has a capacity of zero.

Real world analogy:


Question on Constructor fromCapacityMaxLoadRatio


Recall our DynamicArray. We intialized a new DynamicArray object to have an initial capacity. For example the array might have a capacity of 10 (meaning ten blank/null slots). It would initially have a size of 0 (zero actual elements).

Capacity and size are used similarily for a HashTable. Capacity is the available space and size is the actual # of keys (or associations).

See example calcs.

Also be sure to see the examples for "static factory methods".

What is the relationship between the HashTable class and Association class?


I want you to be able to go from design to code.

So, take a look here:


Do you now see the relationship with Association? Write out the instance variable declarations and that will also help.

Also, more info here on the relationship:


Can I return size for the method keys?


No, here is the ADT description of keys:

Return list containing all keys (order of keys is not specified) - return type is a DynamicList

And the provided method header (in the provided Java interface) is:

DynamicList keys()

Examples:


But note that, in your code, you don't have to worry about Integer, String etc. that will be taken care of for you by the method header because it specifies a list element type K so Java is smart enough to know when you add a key into your result list it will have the correct type (generics constrains it).

Are my instance variables correct?


Here are my instance variables. Are they correct?

DynamicArray buckets;
int maxLoadRatio = 3;
int _size;

You are heading in the right direction. Here is what I would suggest:

private DynamicList<LinkedList<Association<K, V>>> buckets;
private double maxLoadRatio;
private int size;

public static final int GROWTH_FACTOR = 2;
public static final int DEFAULT_INITIAL_SIZE = 17;
public static final double DEFAULT_MAX_LOAD_RATIO = 0.75;

And for constructors, something like:

//=====================================================
//Constructors

public HashTable(int initCapacity, double aMaxLoadRatio) {
	initTable(initCapacity);
	this.maxLoadRatio = aMaxLoadRatio;
}

public HashTable() {
	this(DEFAULT_INITIAL_SIZE, DEFAULT_MAX_LOAD_RATIO);
}

Here is a helper:

//=====================================================
//Helpers

private void initTable(int sz) {
	this.buckets = DynamicArray.fromGrowthFactor(GROWTH_FACTOR);
	for (int i = 0; i < sz; i++)
		buckets.add(new LinkedList<>());
	this.size = 0;
}

How are we supposed to utilize bucketCount?


In the concepts chapter (previous chapter) see the "Algorithms" page and then follow the link to "Load Ratio (Keys Per Bucket)". That exaplains how bucketCount is used.

Note that bucketCount is just used as temporary local variable (you could give the var a different name if you like).










































Data Structures And Algorithms (DSA) (Chapter 602 - Hash Table Object Design)










Chapter 602 - Hash Table Object Design FAQs for Hash Table Coding Challenge

Index Intro Context Headers Size Normalizing Design Design Docs Tips References Challenge

Chapter Top Search Site Contents