Jump to page content Jump to navigation

• Education Policy & Advocacy
• Membership
• Testing
• College Guidance
• K–12 Services
• Higher Ed Services
• Professional Development
• Data, Reports & Research

AP Central

Home > AP Courses and Exams > Course Home Pages > Hash Table and Binary Search Tree Comparison Hash Table and Binary Search Tree Comparison by Rodney Hoffman Occidental College Los Angeles, California More Nifty Assignments... Nifty Assignments Assignment Generate 100 random integers between 1 and 1000, inclusive. Build a binary search tree as you go, and at the same time, using the same numbers, build a hash table. Use a hash table of size 150 and hash function of (n % 150), and use linear probing to resolve collisions. Now search both the binary search tree and the hash table 50 times each, looking for the numbers 20, 40, 60, 80, ..., 980, 1000. Collect statistics on your searches. For the binary search tree, count the number of nodes visited during each search. For the hash table, count the number of array positions examined during each search. At the end, for both data structures, report: Smallest count among the 50 searches Biggest count among the 50 searches Average count among the 50 searches Average count among successful searches Average count among unsuccessful searches Number of successful searches Contribute If you would like to contribute your suggestions for nifty assignments, please submit your ideas. See also... AP Computer Science A Course Home Page AP World History Course Home Page Teachers' Resources

• 1 - Home Page
• 2 - Skip to content
• 3 - Site Map
• 4 - Search field focus
• 6 - Site navigation tree
• 9 - Contact information
• 0 - Access Key details

Back to top