Data structures in Java

Anagram Queries using Hashing

In this assignment you will implement a program which prints out all anagrams of a specified string. Two strings are anagrams of one another if by rearranging letters of one of the strings you can obtain another. For example, the string "stuart" is an anagram of "rattus". For the purpose of this assignment, we are only interested in those anagrams of a given string which appear in the dictionary. The dictionary you should use is the file attached words.txt.

Algorithm and Implementation:

Since we will be performing multiple anagram queries, our first step is to load all of the (~25,000) words in the dictionary into an appropriate data structure. A primary requirement is that one must be able to efficiently search this data structure to look for anagrams of a given word. A clever trick that we will use to facilitate this is to first sort the letters of every word we insert into our data structure (you may use any sort you wish -- even one from the Java API) to produce a key for each word. For example, the key for the string "stuart" is "arsttu", similarly the key for both "star" and "rats" is "arst". (Expert Scrabble players will recognize this procedure as computing the alphagram of a set of letters). We will then use a hash table to store pairs of strings, where the pair consists of the original word and its key. You must write a little class to represent this pair of strings (perhaps call it Anagram).

When performing insertions into the hash table, we will compute the hash value of the key/alphagram of the word to compute the correct bucket (location in the hash table). This approach guarantees that all words which are anagrams of one another are stored in the same bucket of the hash table. Similarly, when we are searching for anagrams, we will first compute the key of the word we are searching for, then hash the key, then search that bucket for anagram matches. You should feel free to use the methods described in the text and in class for appropriate hash functions for hashing strings (please cite any source which you use). Also, make sure your function is efficient and does not hash completely unrelated sets of anagrams to the same bucket *if possible*. If it does, handle the collisions as you see fit (Open Addressing,

Chaining, whatever -- BTW: you may use the Java API for your linked list(s) if you go that route). Also note that if you must probe for a given set of anagrams in time greater than or equal to O(log2n), then you must revise your hash function. You will be graded heavily on the performance of your function. NOTE: you are *NOT* allowed to use the hashCode method from the String class to do your work -- you must write your own hash function. Furthermore, you are NOT allowed to use the Java API (Hashtable/HashMap/HashSet) for your hash table -- you need to create an array for that.

Your code should contain features to count how many collisions occur when placing words from the dictionary into your hash table. At program completion, report how many words were placed and how many collisions occurred. This output will be to the monitor/console (System.out). Any time you try and place a word and the hash table has a word at that location that does NOT have the same key, that counts as a collision.

Details:

The hash table code which you provide only needs to have the minimum functionality necessary for this assignment (it does not have to be generic). You should fix a size for your hash table for efficient searching. For debugging your code, you should work with a much smaller practice dictionary, perhaps 10 words, and a much smaller hash table, perhaps 15-20 buckets (depending on whether or not there are any anagrams in the dictionary). Make sure your table size is prime to help reduce collisions. Remember it is ok to sacrifice space for speed -- that is what hashing is all about. That said, your table should not be bigger than 200,000. Try different table sizes in conjunction with your hash function. Modify the table size and/or function accordingly until you reach a 'sweet spot' (a threshold value). You can decide a threshold value.

NOTE: You may disregard any words in the dictionary which contain any punctuation characters. All other words should be included. Also, you should convert any uppercase characters to lowercase (thus you are only representing words that contain all lower case characters). Your program should read anagram queries from a file which has been specified as a command line argument. Each query in the file will be on its own line and will simply consist of a string. The output file (which will also be specified on the command line following the input file) should contain the original string, then the number of matching anagrams, followed by those anagrams. Look at the example input file and the resulting output file. Your output file should match this format exactly, except that the matching anagrams you output may be ordered differently. If run from the command line, executing your program would be done as follows: java HashTester input_file.txt output_file.txt

NOTE: Do not count a word as an anagram of itself.

To Turn In (in an appropriately named zip): All source files (name your tester file -- the one that contains the main method -- HashTester)

the words file (the dictionary of words) the *ROBUST* input file you used for testing the output file your program produced. Include a comment at the top of your Tester file that *clearly* describes how you confirmed your hashing function operated better than O(log2n). Another way to show your hash function is good is to compare it with the API's String hashCode() - if you do better than it does, you are good to go! If you fail to justify that your hash function was better than O(log2n) you will lose 10 points.

EXTRA CREDIT: *Clearly* demonstrate your hash function is better than the Java API's for 10 extra points. Include justification of the extra credit in comments at the top of your tester file.

Output Example One

qiewuro

ssrab

oflg

equiye

Output Example Two

qiewuro 0

ssrab 1 brass

oflg 2 flog golf

equiye 0

Dictionary called words.txt, it is only couple works bc it doesnt let me to post the entire dictionary

10th 1st 2nd 3rd 4th 5th 6th 7th 8th 9th a AAA AAAS Aarhus Aaron AAU ABA Ababa aback abacus abalone abandon abase abash abate abater abbas abbe abbey abbot Abbott abbreviate abc abdicate abdomen abdominal abduct Abe abed Abel Abelian Abelson Aberdeen Abernathy aberrant aberrate abet abetted abetting abeyance abeyant abhorred abhorrent abide Abidjan Abigail abject ablate ablaze able ablution Abner abnormal Abo aboard abode abolish abolition abominable abominate aboriginal aborigine aborning abort abound about above aboveboard aboveground abovementioned abrade Abraham Abram Abramson abrasion abrasive abreact abreast abridge abridgment abroad abrogate abrupt abscess abscissa abscissae absence absent absentee absenteeism absentia absentminded absinthe absolute absolution absolve absorb absorbent absorption absorptive abstain abstention abstinent abstract abstracter abstractor abstruse absurd abuilding abundant abusable abuse abusive abut abutted abutting abysmal abyss Abyssinia AC academe academia academic academician academy Acadia acanthus Acapulco accede accelerate accelerometer accent accentual accentuate accept acceptant acceptor access accessible accession accessory accident accidental accipiter acclaim acclamation acclimate accolade accommodate accompaniment accompanist accompany accomplice accomplish accord accordant accordion accost account accountant Accra accredit accreditate accreditation accretion accrual accrue acculturate accumulate accuracy accurate accusation accusative accusatory accuse accustom ace acerbic acerbity acetate acetic acetone acetylene ache achieve Achilles aching achromatic acid acidic acidulous Ackerman Ackley acknowledge acknowledgeable ACM acme acolyte acorn acoustic acquaint acquaintance acquiesce acquiescent acquire acquisition acquisitive acquit acquittal acquitting acre acreage acrid acrimonious acrimony acrobacy acrobat acrobatic acronym acropolis across acrylate acrylic ACS act Actaeon actinic actinide actinium actinolite actinometer activate activation activism Acton actor actress Acts actual actuarial actuate acuity acumen acute acyclic ad Ada adage adagio Adair Adam adamant Adams Adamson adapt adaptation adaptive add added addend addenda addendum addict Addis Addison addition additional additive addle address addressee Addressograph adduce Adelaide Adele Adelia Aden adenine adenoma adenosine adept adequacy adequate adhere adherent adhesion adhesive adiabatic adieu adipic Adirondack adjacent adject adjectival adjective adjoin adjoint adjourn adjudge adjudicate adjunct adjust adjutant Adkins Adler administer administrable administrate administratrix admiral admiralty admiration admire admissible admission admit admittance admitted admitting admix admixture admonish admonition ado adobe adolescent Adolph Adolphus Adonis adopt adoption adoptive adore adorn adposition adrenal adrenaline Adrian Adriatic Adrienne adrift adroit adsorb adsorbate adsorption adsorptive adulate adult adulterate adulterous adultery adulthood advance advantage advantageous advent adventitious adventure adventurous adverb adverbial adversary adverse advert advertise advice advisable advise advisee advisor advisory advocacy advocate Aegean aegis Aeneas Aeneid aeolian Aeolus aerate aerial Aerobacter aerobic aerodynamic aerogene aeronautic aerosol aerospace Aeschylus aesthete aesthetic afar affable affair affect affectate affectation affectionate afferent affiance affidavit affiliate affine affinity affirm affirmation affirmative affix afflict affluence affluent afford afforest afforestation affricate affront Afghan Afghanistan aficionado afield afire aflame afloat afoot aforementioned aforesaid aforethought afoul afraid afresh Africa afro aft aftereffect afterglow afterimage afterlife aftermath afternoon afterthought afterward afterword again against Agamemnon agate Agatha agave age Agee agenda agent agglomerate agglutinate agglutinin aggravate aggregate aggression aggressive aggressor aggrieve aghast agile aging agitate agleam Agnes Agnew agnomen agnostic ago agone agony agouti agrarian agree agreeable agreed agreeing agribusiness Agricola agricultural agriculture agrimony ague Agway ah ahead ahem Ahmadabad Ahmedabad ahoy aid Aida aide Aides Aiken ail ailanthus aile Aileen aileron aim ain't Ainu air airborne aircraft airdrop airedale Aires airfare airfield airflow airfoil airframe airlift airline airlock airmail airman airmass airmen airpark airplane airport airspace airspeed airstrip airtight airway airy aisle Aitken ajar Ajax AK Akers akin Akron AL ala Alabama Alabamian alabaster alacrity alai Alameda Alamo Alan alan alarm Alaska alb alba albacore Albania Albanian Albany albatross albeit Alberich Albert Alberta Alberto Albrecht Albright album albumin Albuquerque Alcestis alchemy Alcmena Alcoa alcohol alcoholic alcoholism Alcott alcove Aldebaran aldehyde Alden alder alderman aldermen Aldrich aldrin ale Alec Aleck aleph alert alewife Alex Alexander Alexandra Alexandre Alexandria Alexei Alexis alfalfa Alfonso alfonso Alfred Alfredo alfresco alga algae algaecide algal algebra algebraic Algenib Alger Algeria Algerian Algiers alginate Algol Algonquin algorithm algorithmic Alhambra Ali alia alias alibi Alice Alicia alien alienate alight align alike alimony aliphatic aliquot Alison Alistair alive alizarin alkali alkaline alkaloid alkane alkene all Allah Allan allay allegate allegation allege Allegheny allegiant allegoric allegory Allegra allegro allele allemand Allen Allentown allergic allergy alleviate alley alleyway alliance allied alligator Allis Allison alliterate allocable allocate allot allotropic allotted allotting allow allowance alloy allspice Allstate allude allure allusion allusive alluvial alluvium ally allyl Allyn alma Almaden almagest almanac almighty almond almost aloe aloft aloha alone along alongside aloof aloud alp alpenstock Alpert alpha alphabet alphabetic alphameric alphanumeric Alpheratz Alphonse alpine Alps already Alsatian also Alsop Altair altar alter alterate alteration altercate alterman altern alternate althea although altimeter altitude alto altogether Alton altruism altruist alum alumina aluminate alumna alumnae alumni alumnus alundum Alva Alvarez alveolar alveoli alveolus Alvin alway always alyssum A&M am AMA Amadeus amalgam amalgamate amanita amanuensis amaranth Amarillo amass amateur amateurish amatory amaze Amazon ambassador amber ambiance ambidextrous ambient ambiguity ambiguous ambition ambitious ambivalent amble ambling ambrose ambrosia ambrosial ambulant ambulate ambulatory ambuscade ambush Amelia ameliorate amen amend amende Amerada America American Americana Americanism americium Ames Ameslan amethyst amethystine Amherst ami amicable amid amide amidst amigo amino aminobenzoic amiss amity Amman Ammerman ammeter ammo ammonia ammoniac ammonium ammunition amnesia Amoco amoeba amoebae amok among amongst amoral amorous amorphous amort Amos amount amp amperage ampere ampersand Ampex amphetamine amphibian amphibious amphibole amphibology amphioxis ample amplifier amplify amplitude amply amputate amputee amra Amsterdam Amtrak amulet amuse Amy amy amygdaloid an ana Anabaptist Anabel anachronism anachronistic anaconda anaerobic anaglyph anagram Anaheim analeptic analgesic analogous analogue analogy analyses analysis analyst analytic anamorphic anaplasmosis anarch anarchic anarchy Anastasia anastigmat anastigmatic anastomosis anastomotic anathema Anatole anatomic anatomy ancestor ancestral ancestry anchor anchorage anchorite anchoritism anchovy ancient ancillary and Andean Andersen Anderson Andes andesine andesite andiron Andorra Andover Andre Andrea Andrei Andrew Andrews Andromache Andromeda Andy anecdotal anecdote anemone anent anew angel Angela Angeles angelfish angelic Angelica Angelina Angeline Angelo anger Angie angiosperm angle Angles Anglican Anglicanism angling Anglo Anglophobia Angola Angora angry angst angstrom anguish angular Angus anharmonic Anheuser anhydride anhydrite anhydrous ani aniline animadversion animadvert animal animate animism animosity anion anionic anise aniseikonic anisotropic anisotropy Anita Ankara ankle Ann Anna annal Annale Annalen annals Annapolis Anne anneal Annette annex Annie annihilate anniversary annotate announce annoy annoyance annual annuity annul annular annuli annulled annulling annulus annum annunciate anode anodic anomalous anomaly anomie anonymity anonymous anorexia anorthic anorthite anorthosite another Anselm Anselmo ANSI answer ant antacid Antaeus antagonism antagonist antagonistic antarctic Antarctica Antares ante anteater antebellum antecedent antedate antelope antenna antennae anterior anteroom anthem anther anthology Anthony anthracite anthracnose anthropogenic anthropology anthropomorphic anthropomorphism anti antic anticipate anticipatory Antietam antigen Antigone antigorite antimony Antioch antipasto antipathy antiperspirant antiphonal antipode antipodean antipodes antiquarian antiquary antiquated antique antiquity antisemite antisemitic antisemitism antithetic antler Antoine Antoinette Anton Antonio Antony antonym Antwerp

anvil anxiety anxious any anybody anybody'd anyhow anyone anyplace anything anyway anywhere aorta A&P apace apache apart apartheid apathetic apathy apatite ape aperiodic aperture apex aphasia aphasic aphelion aphid aphorism Aphrodite apices apiece aplomb apocalypse apocalyptic Apocrypha apocryphal apogee Apollo Apollonian apologetic apologia apology apostate apostle apostolic apostrophe apothecary apothegm apotheosis Appalachia appall appanage apparatus apparel apparent apparition appeal appear appearance appeasable appease appellant appellate append appendage appendices appendix apperception appertain appetite Appian applaud applause apple Appleby applejack Appleton appliance applicable applicant applicate application applied applique apply appoint appointe appointee apport apportion apposite apposition appraisal appraise appreciable appreciate apprehend apprehension apprehensive apprentice apprise approach approbation appropriable appropriate approval approve approximable approximant approximate Apr apricot April apron apropos APS apse apt aptitude aqua aquarium Aquarius aquatic aqueduct aqueous Aquila Aquinas AR Arab arabesque Arabia Arabic Araby Arachne arachnid arbiter arbitrage arbitrary arbitrate arboreal arboretum arbutus arc arcade Arcadia arcana arcane arccos arccosine arch archae archaic archaism archangel archbishop archdiocese archenemy Archer archery archetype archetypical archfool Archibald Archimedes arching archipelago architect architectonic architectural architecture archival archive arcing arclength arcsin arcsine arctan arctangent arctic Arcturus Arden ardency ardent arduous are area areaway areawide arena arenaceous aren't Arequipa Ares Argentina argillaceous arginine Argive argo argon Argonaut Argonne argot argue argument argumentation argumentative Argus arhat Ariadne Arianism arid Aries arise arisen aristocracy aristocrat aristocratic Aristotelean Aristotelian Aristotle arithmetic Arizona ark Arkansan Arkansas Arlen Arlene Arlington arm armada armadillo Armageddon armament Armata armature armchair Armco Armenia Armenian armful armhole armillaria armistice armload armoire Armonk Armour armpit Armstrong army Arnold aroma aromatic arose around arousal arouse ARPA arpeggio arrack Arragon arraign arrange arrangeable array arrear arrest Arrhenius arrival arrive arrogant arrogate arrow arrowhead arrowroot arroyo arsenal arsenate arsenic arsenide arsine arson art Artemis artemisia arterial arteriole arteriolosclerosis arteriosclerosis artery artful arthritis Arthur artichoke article articulate articulatory Artie artifact artifice artificial artillery artisan artistry Arturo artwork arty Aruba arum aryl a's as asbestos ascend ascendant ascension ascent ascertain ascetic asceticism ascomycetes ascribe ascription aseptic asexual ash ashame ashamed ashen Asher Asheville Ashland Ashley ashman ashmen Ashmolean ashore ashtray ashy Asia Asiatic aside Asilomar asinine ask askance askew asleep asocial asparagine asparagus aspartic aspect aspen asperity aspersion asphalt aspheric asphyxiate aspidistra aspirant aspirate aspire aspirin asplenium assai assail assailant Assam assassin assassinate assault assay assemblage assemble assent assert assess assessor asset assiduity assiduous assign assignation assignee assimilable assimilate assist assistant associable associate assonant assort assuage assume assumption assurance assure Assyria Assyriology Astarte astatine aster asteria asterisk asteroid asteroidal asthma astigmat astigmatic astigmatism ASTM astonish Astor Astoria astound astraddle astral astray astride astringent astrology astronaut astronautic astronomer astronomic astronomy astrophysical astrophysicist astrophysics astute Asuncion asunder asylum asymmetry asymptote asymptotic asynchronous asynchrony at Atalanta atavism atavistic Atchison ate Athabascan atheism atheist Athena Athenian Athens athlete athletic athwart Atkins Atkinson Atlanta atlantes Atlantic atlantic Atlantica Atlantis atlas atmosphere atmospheric atom atomic atonal atone atop Atreus atrium atrocious atrocity atrophic atrophy Atropos AT&T attach attache attack attain attainder attempt attend attendant attendee attention attentive attenuate attest attestation attic Attica attire attitude attitudinal attorney attract attribute attribution attributive attrition attune Atwater Atwood atypic Auberge Aubrey auburn Auckland auction auctioneer audacious audacity audible audience audio audiotape audiovisual audit audition auditor auditorium auditory Audrey Audubon Auerbach Aug Augean augend auger augite augment augmentation augur august Augusta Augustan Augustine Augustus auk aunt auntie aura aural Aurelius aureomycin auric Auriga aurochs aurora Auschwitz auspices auspicious austenite austere Austin Australia Australis australite Austria authentic authenticate author authoritarian authoritative autism autistic auto autobiography autoclave autocollimate autocorrelate autocracy autocrat autocratic autograph automat automata automate automatic automaton automobile automorphic automorphism automotive autonomic autonomous autonomy autopsy autosuggestible autotransformer autumn autumnal auxiliary avail avalanche avarice avaricious Ave avenge Aventine avenue aver average averred averring averse aversion avert avertive Avery Avesta aviary aviate aviatrix avid avionic Avis Aviv avocado avocate avocation avocet Avogadro avoid avoidance Avon avow avowal avuncular await awake awaken award aware awash away awe awesome awful awhile awkward awl awn awoke awry ax axe axes axial axiology axiom axiomatic axis axisymmetric axle axolotl axon aye Ayers Aylesbury AZ azalea Azerbaijan azimuth azimuthal Aztec Aztecan azure b babbitt babble Babcock babe Babel baboon baby babyhood Babylon Babylonian babysat babysit babysitter babysitting baccalaureate baccarat Bacchus Bach bachelor bacilli bacillus back backboard backbone backdrop backfill backgammon background backhand backlash backlog backorder backpack backplane backplate backscatter backside backspace backstage