Implementation and use of data structures in Java programs. http://patricklam.ca/dsfinder

Programs manipulate data. For many classes of programs, this data is organized into data structures. Java’s standard libraries include robust, general-purpose data structure implementations; however, standard implementations may not meet developers ’ needs, forc-ing them to implement ad-hoc data structures. We investigate the implementation and use of data structures in practice by develop-ing a tool to statically analyze Java libraries and applications. Our DSFinder tool reports 1) the number of likely and possible data structure implementations in a program and 2) characteristics of the program’s uses of data structures. We applied our tool to 62 open-source Java programs and manually classified possible data struc-tures. We found that 1) developers overwhelmingly used Java data structures over ad-hoc data structures; 2) applications and libraries confine data structure implementation code to small portions of a software project; and 3) the number of ad-hoc data structures corre-lates with the number of classes in both applications and libraries, with approximately 0.020 data structures per class. 1