Sachverhalt: A. A.a. Am 24. Januar 2015 soll sich X._ gemäss Darstellung der Kantonspolizei Basel-Stadt einer polizeilichen Kontrolle widersetzt und die Polizisten bei ihrer Amtshandlung behindert haben. X._ seinerseits wirft den Polizeibeamten vor, ihr Einsatz sei illegal gewesen, sie hätten ihm verschiedene Verletzungen zugefügt und unerlaubterweise einen Taser eingesetzt. Mit Strafbefehl der Staatsanwaltschaft Basel-Stadt vom 18. Juni 2015 wurde X._ wegen mehrfacher Widerhandlung gegen das Übertretungsstrafgesetz des Kantons Basel-Stadt zu einer Busse von 800.-- CHF bzw. bei schuldhafter Nichtbezahlung ersatzweise zu einer Freiheitsstrafe von acht Tagen verurteilt. Das Verfahren gegen die Polizisten ist bei der Staatsanwaltschaft hängig. A.b. X._ erhob am 29. Juni 2015 Einsprache gegen den Strafbefehl, woraufhin die Staatsanwaltschaft die Sache dem Strafgericht überwies. Mit Verfügung vom 25. August 2015 teilte die verfahrensleitende Strafgerichtspräsidentin Y._ der Verteidigung von X._ die vorgesehenen Beweiserhebungen mit und stellte Frist für allfällige weitere Beweisanträge. Ohne die Abnahme weiterer Beweise zu verlangen, beantragte X._ am 30. Oktober 2015 die Sistierung des Verfahrens bis zum Abschluss der gegen die Polizeibeamten gerichteten Strafuntersuchung. Die Strafgerichtspräsidentin wies das Sistierungsgesuch am 2. November 2015 ab. Einen in der Folge eingereichten Antrag auf Rückweisung des Verfahrens an die Staatsanwaltschaft wies die Strafgerichtspräsidentin am 1. Dezember 2015 ebenfalls ab und entschied zugleich über die am 26. November 2015 von der Verteidigung eingereichten Beweisanträge. Bei der Hauptverhandlung im Einspracheverfahren am 12. Januar 2016 wies die Strafgerichtspräsidentin ein erneutes Gesuch der Verteidigung auf Rückweisung und eventuell Sistierung des Verfahrens wiederum ab. Daraufhin beantragte die Verteidigung den Ausstand von Y._ wegen Befangenheit. Die Hauptverhandlung musste in der Folge aus einem anderen Grund ausgesetzt werden. B. Am 12. Januar 2016 überwies die Strafgerichtspräsidentin das Ausstandsgesuch dem Appellationsgericht des Kantons Basel-Stadt mit dem Antrag auf Abweisung des Antrags. Mit Entscheid vom 18. Februar 2016 wies das Einzelgericht am Appellationsgericht das Ausstandsgesuch ab. C. Mit Beschwerde in Strafsachen an das Bundesgericht vom 11. April 2016 beantragt X._, den Entscheid des Appellationsgerichts aufzuheben und festzustellen, dass Y._ in den Ausstand zu treten habe; eventuell sei der Entscheid des Appellationsgerichts aufzuheben und im Sinne der Erwägungen an dieses zu neuem Entscheid zurückzuweisen. Zur Begründung wird im Wesentlichen ausgeführt, wegen Voreingenommenheit der Verfahrensleiterin am Strafgericht sei ein faires Verfahren ausgeschlossen. Y._ schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten sei. Das Appellationsgericht stellt Antrag auf Abweisung. X._ äusserte sich am 10. und 31. Mai 2016 nochmals zur Sache.