Can anyone help me do this hash table program? I just need the program. Hash tab
ID: 3829469 • Letter: C
Question
Can anyone help me do this hash table program? I just need the program.
Hash table collision algorithm analysis
In this project, you need to build a hash table using two different algorithms for collision resolution that we discussed in lecture – open addressing and chaining. Your hash table should be build from the provided data set on Moodle called playerData. You also need to evaluate the performance of each algorithm in terms of how many collisions are generated while the table is built and the operations required to retrieve data from the table. Your evaluation and the results need to be described in a 2 - 3 page paper, single-spaced, 12pt. Times New Roman font.
Assignment data if you need the data plz leave your email, because this file is a little big. I cannot copy and post here.
There is a file on Moodle called playerData that includes every Major League Baseball player on every team since 1985. For example, the first two rows in the file show the header row, which shows what each column includes, and the first row of data. The first row of data is:
1985, ATL, NL, barkele01, 870000, Len, Barker, 1955, USA, 225, 77, R, R
The fields in the header row show:
yearID – year, between 1985 and 2016
teamID – three-letter abbreviation for team
leagueID – league that the team belongs to, either National League (NL) or American League (AL)
playerID – ID for the player, used in the Lahman database where I downloaded data
salary – how much money the player made that year
firstName – player’s first name
lastName – player’s last name
birthYear – year the player was born
birthCountry – country where the player was born
weight – player’s weight
height – player’s height
bats – how the player bats, either right (R ) or left (L) handed, or switch (S).
throws – how the player throws, either right (R ) or left (L) handed.
Assignment requirements
Build hash table You need to process the data provided and build a hash table, where the key for entries in the hash table is the player’s first and last name, concatenated. For example, for the first row in the file, the key would be LenBarker. For a hash function, you can use the hashSum function discussed in lecture, or any other hash function that you want to try. In your project report, describe the hash function that you use. Each player should only appear in the hash table one time. Each record in the hash table needs to include the player’s information, including first and last name, birth year and country, height and weight, and batting and throwing. Each record also needs to include a list of all the teams and years that the player was active, and their salary for that year. For example, the hash table entry for Len Barker would be:
First name: Len
Last name: Barker
Year born: 1955
Country born: USA
Weight: 225
Height: 77
Bats: R
Throws: R
Teams and salary: 1985, ATL, NL, 870000
1986, ATL, NL, 880000
1987, ATL, NL, 890000
1987, ML4, AL, 72500
1988, ATL, NL, 900000
The teams and salary entries are taken from the playerData file for every row where the player’s name appears. Note: you could have multiple players with the same name. You will need some method for verifying the uniqueness of a player. For example, if there were another Len Barker in the data file, you might want to check the height and weight or year born information to determine if it’s the same person.
Set hash table size using command line argument
Use a command line argument to set the size of the hash table. There are 5072 unique players in the playerData file. Run your program multiple times, using 5072 as the minimum hash table size, and increase the size of the hash table up to 15K- 20K. In your project write up, describe the effect that increasing the hash table size had on the number of collisions for both algorithms.
Collision analysis
As part of this assignment, you need to evaluate the performance of two collision resolution algorithms – open addressing and chaining. My suggestion for approaching this problem is to build two hash tables as you are reading the data from the file – one hash table resolves collisions using open addressing and the other hash table resolves collisions using chaining.
Collisions during building the table
As you are building the hash table, you need to count the number of collisions that each collision resolution algorithm generates. You also need to count the number of search operations needed to find a location for the record. For example, if you are using chaining and there is a collision and you traverse three records in a linked list to find an open location, then the number of search operations is 3. If you get a collision using open addressing and evaluate 4 entries in the hash table before finding an open location, then the number of search operations is 4. Once the table is built, display the following information clearly for the user:
Hash table size: <tablesize>
Collisions using open addressing:<collisions>
Collisions using chaining: <chaining collisions>
Search operations using open addressing: <search ops>
Search operations using chaining:<search ops chaining>
User input
Your program needs to present the user with the option of looking up a player in the hash table. A suggested menu is as follows:
1. Query hash table
2. Quit program
If the user selects Query hash table, they should be asked to input the name of a player. If the player is in the hash table, display the record for that player, including all of the information shown on the previous page for the Len Barker example. If the player is not in the hash table, display “Player not found”, and display the menu again so the user can select another player or quit the program.
Linear searches needed to retrieve data
In addition to displaying player information, your program should also display the number of search operations needed to find the player in the hash table for both open addressing and chaining. For example, if the hash code for a player is 0, and no other players are stored at that index, then there would be zero searches needed to find the players information. However, if there are 5 players with the same hash code, and the player you need was stored at the end of the linked list for that index using chaining, then the number of searches is 5.
Display the following information, in addition to the player information:<search ops>
Search operations using open addressing: <search ops chaining>
Search operations using chaining:
Explanation / Answer
The Hash table algorithm can be solved using both Open Addressing and Collision techniques.
When the two or more keys are mapped to the same address or location in the hash table then it is termed as collision.
The separate chaining methods are used to have a good hash table. The keys which map to the same hash value will be kept in the bucket.
The three methods used in the algorithm are as follows:
Algorithm:
//The hash object returns the specified value
static int hash (Object x)
{
int hx=x. hash Code ();
return hx;
}
//It is used to return the index value
static int hash Index (int hx, int length)
{
return hx&(length-1);
}
//The get operation maps to the same location in a hash table
public Object get (Object key)
{
int hash= hash(key);
int i=hash Index (hash, hashTable.length);
Entry e=hash Table[i];
while(true)
{
if(e==null)
return e;
if (e. hash==hash&&eq (k, e.key))
return e.value;
e=e. next;
}
}
//The put method is used for replacing the existing key with the new key
public Object put (Object key, Object value)
{
int hash=hash(key);
int i=hash Index (hash, hashTable.length);
for (Entry e=hash Table[i]; e! =null; e=e. next)
{
if (e. hash==hash && eq (k, e.key))
{
Object old Value=e.value;
e.value=value;
return old Value;
}
}
new Hash Entry (hash, k, value, i);
return null;
}
//This method helps in adding the new entries in the hash table
void new Hash Entry (int hash, Object key, Object value, int indexBucketValue)
{
hash Table[indexBucketValue] = new Entry (hash, key, value, hash Table[indexBucketValue]);
if (size++ >= threshold)
resize (2 * hashTable.length);
}
/* The remove method is helpful in removing keys from the table */
public Object remove (Object key)
{
Entry e = hashRemoveKey(key);
return (e == null? e: e.value);
}
/* This operation is used to check the null value present or not in the given table */
Entry hashRemoveKey (Object key)
{
int hash = hash(key);
int i = hash Index (hash, hashTable.length);
Entry prev = hash Table[i];
Entry e = prev;
while (e! = null) {
Entry next = e. next;
if (e. hash == hash && eq (k, e.key))
{
size--;
if (prev == e)
hash Table[i] = next;
else
prev. next = next;
return e;
}
prev = e;
e = next;
}
return e;
}
B) Open Addressing: -
In open addressing, the linear probing technique plays a vital role in placing the keys into the hash table by checking all the conditions and occupies the location for it.
The linear probing technique can be shown by the following diagram:
After inserting 59
Index
Element
0
1
2
3
4
5
6
7
8
9
59
After inserting 16
Index
Element
0
1
2
3
4
5
6
7
8
16
9
59
After inserting 36
Index
Element
0
36
1
2
3
4
5
6
7
8
16
9
59
The values are inserted per the following hash functions:
hash (59,10) = 9
hash (16,10) =8
hash (36,10) =9
Index
Element
0
1
2
3
4
5
6
7
8
9
59
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.